Prove by induction that every natural number $n$ has a natural number $k$ and numbers $a_{0} , a_{1},..., a_{k}\in \left \{ 0,1 \right \}$ such that $n=\sum_{i=0}^{k} a_{i} 2^{i}$
I really don't understand What should I do here? I guess it's related to a binary base but how to start solving this question? Thanks!
You've correctly detected that this is connected with the binary expression for $n$. You need to do three things now: (1) Figure out exactly what that connection is, i.e., if I gave you the binary expression for $n$, say 110101 when n=53, how could you easily find the $a_i$'s? (2) Prove the base case of the desired induction, i.e., prove that the result is correct for $n=0$ (or $n=1$ if your natural numbers begin with $1$). (3) Prove the induction step, i.e., assuming the desired result for $n$ prove it for $n+1$. In part (3), it will be useful to understand exactly how adding $1$ works in binary notation, in particular what "carrying" occurs. Once you understand that in terms of binary notation, you can use (1) to express it in terms of the $a_i$'s and so complete the induction proof.