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

Problem:

1. Find the general formula for $a_{n+1}=2^n a_n +4$, where $a_1=1$.
2. 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?
• Where does this problem come from? Aug 4, 2015 at 8:30
• @user37238 Distributed among QQ groups. It is highly suspicious. Aug 4, 2015 at 8:32

• One might be able to calculate it using the Cauchy residue theorem by finding a function with residues only at the integers $0$ through $n-1$ agreeing with the summands, then computing a contour integral... Aug 4, 2015 at 9:06
You can proceed backward in order to "guess" the solution and then prove it properly by induction. I mean: $a_n=2^{n-1}a_{n-1}+4=2^{n-1}(2^{n-2}a_{n-2}+4) + 4=2^{(n-1)+(n-2)}a_{n-2}+4*2^{n-1}+4=\dots$
Doing this you can see what it will look like when you have $a_1$ instead of $a_{n-2}$ (you can make a few more steps if necessary). Once it's done, you just have to simplify it, then prove it by induction if you want to be really rigorous.