Let $N$ be a natural number. Then there certainly exists a unique non-negative integer $k$ such that \[ 2^{k+1} -1 \le N < 2^{k+2}-1 \]Then we have an integer $T=N-(2^{k+1} -1)$ such that \[ 0 \le N-(2^{k+1} -1) < 2^{k+1} \]Hence the number of digits of the binary expression of $T$ is less than or equal to $k+1$. Let $b_0$, $b_1$, $\ldots$, $b_k$ be the binary digits of $T$ \[ T = b_0 2^0 + b_1 2^1 + \cdots + b_k 2^k \]Then $a_0 = b_0+1$, $a_1 = b_1 +1$, $\ldots $, $a_k =b_k +1$ solves the required existence.

Suppose that \begin{align*} N = c_0 2^0 + c_1 2^1 + \cdots + c_{n + 1} 2^{n + 1} \end{align*}is the base $2$ representation of $N$; that is, for constants $c_i \in \{0, 1\}$ with $0 \leq i \leq n + 1$ for some positive integer $n$. In particular, $c_{n+1} = 1$. We consider two cases. Case 1: It is true that $c_i = 1, \forall c_i$. Proof. This case is trivial, as the base $2$ representation of $N$ suffices for the problem; $k$ exists as $k = n + 1$. $\square$ Case 2: The condition in Case 1 is false. Note that \begin{align} 2^{n + 1} - 1 = 1 \cdot 2^0 + 1 \cdot 2^1 + \cdots + 1 \cdot 2^n, \end{align}which can be proved easily via the geometric series formula. Since $c_{n + 1} = 1$, we write the largest term in the base $2$ expansion of $N$ as \begin{align*} c_{n + 1} 2^{n + 1} = 2^{n + 1} = 2 \cdot 2^0 + 1 \cdot 2^1 + \cdots + 1 \cdot 2^n, \end{align*}which follows from $(1)$. Now, we write $N$ in the following manner: \begin{align*} N &= c_0 2^0 + c_1 2^1 + \cdots + c_n 2^n \\ &+ c_{n + 1} 2^{n + 1} \\ &= c_0 2^0 + c_1 2^1 + \cdots + c_n 2^n \\ &+ 2 \cdot 2^0 + 1 \cdot 2^1 + \cdots + 1 \cdot 2^n, \end{align*}and thus we consider the construction \begin{align*} N = (c_0 + 2) 2^0 + (c_1 + 1) 2^1 + \cdots + (c_n + 1) 2^n. \end{align*} Subcase 2.1: Suppose that $c_0 = 0$. Proof. Since $c_0 + 2 = 2$, and for all $c_i$ except $c_0$, $0 \leq c_i \leq 1$, we know that $1 \leq c_i + 1 \leq 2$. Now, we let $a_0 = c_0 + 2$, and $a_i = c_i + 1$ for all $c_i$ except $c_0$, and the construction holds; $k$ exists as $k = n$. $\square$ Subcase 2.2: Suppose that $c_0 = 1$. Proof. Since the condition given in Case 1 is assumed to be false, we know there exists some $c_i$ with $i \neq 0, n$ such that $c_i + 1 = 1$. $(2)$ Now, for every term in the base $2$ expansion of $N$, we proceed with the following process (for context, the informal description of the process is essentially "carry-forward as necessary"). Let the coefficient of $2^j$ in the $(j + 1)$-th term of the expansion be $b_j$. Begin with $j = 0$, such that $b_0 = c_0 + 2 = 3$. If $b_j = 3$, then reassign $b_j$ to $1$, and assign $b_{j + 1}$ to $b_{j + 1} + 1$. This clearly does not change the value of $N$. If $b_j \neq 3$, end the process. Repeat this process for the proceeding term if possible (i.e increment $j$ by $1$). Due to $(2)$, it will eventually be true that $b_{j + 1} = 1$, after which $b_{j + 1} = 2$, and the process terminates as $b_{j + 1} \neq 3$. Thus, after the process terminates, for all $b_j$ we have have that $1 \leq b_j \leq 2$. Letting $a_i = b_i$ for $0 \leq i \leq n$ satisfies the problem statement, and thus $k$ exists as $k = n$. $\square$ This exhausts all of the cases, and we are done. $\blacksquare$