My solution: We use generating functions. Let us define the generating function $F(x)=a_1x+a_2x^2+\cdots$(Indeed, $a_0$ is zero) $\Longrightarrow 2xF(x)=2a_1x^2+2a_2x^3+\cdots$ Also, $\frac{(2x)^2}{1-2x}=2^2x^2+2^3x^3+\cdots$ So, $(1-2x)F(x)-\frac{(2x)^2}{1-2x}=a_1x=2x$ $\Longrightarrow F(x)=\frac{2x}{(1-2x)^2}$ We have $\frac{1}{(1-x)^2}=1+2x+3x^2+\cdots$ by binomial theorem So, replacing $x$ by $2x$, we get $\frac{1}{(1-2x)^2}=1+2\cdot 2^1x+3\cdot 2^2+\cdots$ $\Longrightarrow F(x)=\frac{2x}{(1-2x)^2}=2x+2\cdot 2^2x^2+3\cdot 2^3x^3+\cdots$ So, $a_n=n\cdot 2^n$ It can be seen that if $n$ is a power of $2$, then so is $a_n$ Alternate way: Guess $a_n=2^n\cdot n$ and prove it by mathematical induction.

Lemma: If $m,k \in \mathbb{N}, m+1 \geq k \geq 1$, then $a_{m+1}=2^ka_{m+1-k}+k2^m$. Let prove that by induction to $k$. Base for $k=1$ true by condition. Let for any $k \leq m$ it is true. Prove, that it is true for $k+1$. $a_{m+1}=2^ka_{m+1-k}+k2^m=2^k(2a_{m+1-(k+1)}+2^{m-k})+k2^m$(by condition for $n=m-k$)=$2^{k+1}a_{n+1-(k+1)}+(k+1)2^m$=> $QED$. To problem: After substitution $k=m+1$ to lemma we have $a_m=2^{m+1}a_0+(m+1)2^m=(m+1)2^m$=> If $m+1=2^x$ then $a_{m+1}=2^{x+m}$=> $QED$ P.S. inverse is true, too

Nice solution

Prove, that for all nonnegative $a_0$ exist infinity $n$, such that $a_n$ is natural power of $2$. ($a_n =2a_{n-1}+2^{n-1}$)

Generally speaking, Japanese High School Students don't know generating function, so am I. But solving the reccurence is easy for them. $a_{n+1}=2a_n+2^n\Longleftrightarrow \frac{a_{n+1}}{2^{n+1}}=\frac{a_n}{2^n}+\frac 12$ $\therefore \frac{a_n}{2^{n}}=\frac{a_0}{2}+\frac 12 n=\frac 12 n$, yielding $\boxed{a_n=n\cdot 2^{n-1}\ (n\geq 0)}$.

Ovchinnikov Denis wrote: Prove, that for all nonnegative $a_0$ exist infinity $n$, such that $a_n$ is natural power of $2$. ($a_n =2a_{n-1}+2^{n-1}$) Let $a_0=a\ge 0$ and let $k$ be a whole number such that $2^k\le a<2^{k+1}$. One can use generating functions to derive that $a_n=2^{n-1}(2a+n)$ for all natural $n$ and choosing $n=2^{k+2+s}-2a$ for all whole numbers $s$ provides us $a_n=2^{n+k+s+1}$ as required.

gouthamphilomath wrote: Guess $a_n=2^n\cdot n$ and prove it by mathematical induction. Sorry, that's wrong.