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?
  • $\begingroup$ Where does this problem come from? $\endgroup$
    – user37238
    Commented Aug 4, 2015 at 8:30
  • $\begingroup$ @user37238 Distributed among QQ groups. It is highly suspicious. $\endgroup$
    – Colliot
    Commented Aug 4, 2015 at 8:32

3 Answers 3


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 ... :-)


\begin{align*} a_{n+1}&=2^{n}a_{n}+4\\&=2^{n+(n-1)}a_{n-1}+4\cdot 2^{n}+4\\&=2^{n+(n-1)+(n-2)}a_{n-2}+ 4\cdot 2^{n+(n-1)} + 4\cdot 2^n + 4\\&=2^{n(n+1)/2}+4(1+\sum_{j=0}^{n-1} 2^{\sum_{k=j+1}^n k})\\&=2^{n(n+1)/2}+4(1+\sum_{j=0}^{n-1} 2^{n(n+1)/2-j(j+1)/2})\\&=2^{n(n+1)/2}+4(1+2^{n(n+1)/2}\sum_{j=0}^{n-1} 2^{-j(j+1)/2}) \end{align*}

I'm not sure how to evaluate this last sum. Maybe someone else can assist?

  • $\begingroup$ I think there is no closed form. $\endgroup$ Commented Aug 4, 2015 at 8:55
  • $\begingroup$ 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... $\endgroup$ Commented 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .