<s>[INST] Finding the general formula for $a_{n+1}=2^n a_n +4$, where $a_1=1$. Problem:


*

*Find the general formula for $a_{n+1}=2^n a_n +4$, where $a_1=1$.

*Find the sum of its first $2n$ terms with odd subscript.


My effort:


*

*It seems to me that $a_{n+1} / 2^{(n+1)^2/2}=\dfrac{1}{\sqrt{2}}a_n/2^{n^2/2} +4/ 2^{(n+1)^2/2}$, which is $b_{n+1}=\dfrac{1}{2^{1/2}} b_{n} + \dfrac{1}{2^{(n+3)(n-1)/2}}$, where $b_n=a_n/2^{n^2/2}$. But it seems hard to deal with the last term.

*The first ten $a_n$ is {1, 6, 28, 228, 3652, 116868, 7479556, 957383172, 245090092036, 125486127122436}, which follows no immediate rule.

*Write the sequence in binary form, I find it {1, 110, 11100, 11100100, 111001000100, ...} which is generally in a 1 2*0 1 3*0 1 4*n ... pattern (apart from the first few). So I highly suspect that there is not closed form expression. But how to prove this?

 [/INST] Here is a solution by substitution:
\begin{align}
a_1&=1\\
a_2&=2^1+4\\
a_3&=2^{1+2}+4(1+2^2)\\
a_{1+3}&=2^{1+2+3}+4(1+2^3+2^{3+2})\\
a_{1+4}&=2^{1+2+3+4}+4(1+2^4+2^{4+3}+2^{4+3+2})\\
a_{1+5}&=2^{1+2+3+4+5}+4(1+2^5+2^{5+4}+2^{5+4+3}+2^{5+4+3+2})\\
a_{1+6}&=2^{1+2+3+4+5+6}+4(1+2^6+2^{6+5}+2^{6+5+4}+2^{6+5+4+3}+2^{6+5+4+3+2})\\
...\\
a_{1+n}&=2^{\sum_{j=1}^nj}+4(1+\sum_{j=1}^{n-1}2^{\sum_{k=j+1}^nk})
\end{align}
I should be simplifying this last expression ... but I could not ... :-)
</s>