Q6 Matemática  (IberoAmerican 1994)

Mostre que todo número natural $n\le 2^{1000000}$ pode ser obtido primeiro com 1 fazendo somas inferiores a $1100000$; mais precisamente, existe uma sequência finita de números naturais $x_0,x_1,\dots ,x_k\text{mbox}comk\le 1100000,x_0=1,x_k=n$ tal que para todos $i=1,2,\dots ,k$ existem $r,s$ com $0\le r\le s<i$ tal que $x_i=x_r+x_s$.