I need to solve the recurrence relation $A(n)=2A(n-2)+ 2^{n-2}$. I tried writing out equations up to the $A(2)$ and multiplying by powers of two and adding all the equations together then all the terms cancelled but after that I couldn't find the sum of the powers of two. I forgot to mention that the base is $A(2)=2$ and n is even

  • 1
    $\begingroup$ Do you have a guess for the general term? If so, you can try to prove that your guess is right by induction. $\endgroup$ – Quimey Jul 1 '13 at 20:47
  • $\begingroup$ Unfortunately, I don't . $\endgroup$ – Narek Margaryan Jul 1 '13 at 20:55

Let us compute some values of A(n):

$n=2, A(2)=2$

$n=4, A(4)=2A(2)+2^2=8=2^3$

$n=6, A(6)=2A(4)+2^4=32=2^5$

$n=8, A(8)=2A(6)+2^6=128=2^7$

You should see the pattern, It seems that $A(n)=2^{n-1}$. This is true and can be easily shown by induction.


You do this much the same way as you might solve a differential equation: first find the general solution to the homogeneous part of the equation, and then find a particular solution that you can add to that general solution.

The homogeneous equation here is:

$$ A(n)=2A(n-2) $$

Because $n$ is even, the general solution to this is easily seen to be:

$$ A_C(n)=B.2^{n/2} $$

where $B$ is an arbitrary constant.

We now seek a particular solution. One thing we could try would be just setting:

$$ A_P(n)=2^{n-2} $$

But then $2A_P(n-2)+2^{n-2}=2^{n-1}+2^{n-2}\neq2^{n-2}$.

That didn't work. We somehow need to find some way to make the two terms on the left combine into one term. If we try

$$ A_P(n)=2^{n-1} $$

then we get:

$$ 2A_P(n-2)+2^{n-2}=2^{n-2}+2^{n-2}=2^{n-1}=A_P(n) $$

Thus, $A_P(n)=2^{n-1}$ is a particular solution to the equation. The general solution then is:

$$ A(n)=A_C(n)+A_P(n)=B.2^{n/2}+2^{n-1} $$

Since $A(2)=2$, we have

$$ 2=B.2^1+2^1=2B+2 $$

So $B=0$, and the solution is $A(n)=2^{n-1}$.


It never hurts in such problems to start by gathering some numerical data:

$$\begin{array}{rcc} n:&2&4&6&8&10&12\\ A(n):&2&8&32&128&512&2048\\ A(n):&2^1&2^3&2^5&2^7&2^9&2^{11} \end{array}$$

There’s a very obvious pattern here, that leads to the conjecture that $A(n)=2^{\text{what function of }n?}$ if $n$ is even. Complete the conjecture correctly, and you should have little difficulty using mathematical induction to prove that it’s correct.

Alternatively, let $B(n)=A(2n)$; then $$B(n)=2B(n-1)+2^{2(n-1)}=2B(n-1)+4^{n-1}\;,$$

and ‘unwrap’ the recurrence:

$$\begin{align*} B(n)&=2B(n-1)+4^{n-1}\\ &=2\Big(2B(n-2)+4^{n-2}\Big)+4^{n-1}\\ &=2^2B(n-2)+2\cdot 4^{n-2}+4^{n-1}\\ &=2^2\Big(B(n-3)+4^{n-3}\Big)+2\cdot 4^{n-2}+4^{n-1}\\ &=2^3B(n-3)+2^2\cdot4^{n-3}+2\cdot 4^{n-2}+4^{n-1}\\ &\;\vdots\\ &=2^kB(n-k)+2^{k-1}\cdot 4^{n-k}+2^{k-2}\cdot 4^{n-k+1}+\ldots+2\cdot 4^{n-2}+4^{n-1}\\ &\;\vdots\\ &=2^{n-1}B(1)+\sum_{i=1}^{n-1}2^{i-1}\cdot4^{n-i}\\ &=2^n+\sum_{i=1}^{n-1}2^{i-1}\cdot4^{n-i}\\ &=2^n+\sum_{i=1}^{n-1}2^{i-1}\cdot2^{2n-2i}\\ &=2^n+\sum_{i=1}^{n-1}2^{2n-i-1}\\ &=2^n+\sum_{i=n}^{2n-2}2^i\\ &=2^n+2^n\sum_{i=0}^{n-2}2^i\\ &=2^n\left(1+\sum_{i=0}^{n-2}2^i\right)\\ &=\;? \end{align*}$$


Generating functions to the rescue. Define $g(z) = \sum_{n \ge 0} A(n) z^n$, write: $$ A(n + 2) + 2 A(n) + 2^n $$ Multiply by $z^n$, sum over $n \ge 0$ and recognize the resulting sums to get: $$ \frac{g(z) -A(0) - A(1) z}{z^2} = 2 A(z) + \frac{1}{1 - 2 z} $$ As partial fractions: $$ A(z) = \frac{1 - 2 A(0) - 2 (A(1) - 1) z}{2 (1 - 2 z^2)} + \frac{1}{2 (1 - 2 z)} $$ You could now split the first term into partial fractions (but with irrational coefficients) or just take: \begin{align} \frac{1}{1 - 2 z^2} &= \sum_{n \ge 0} 2^n z^{2 n} \\ \frac{z}{1 - 2 z^2} &= \sum_{n \ge 0} 2^n z^{2 n + 1} \end{align} i.e., split into even and odd cases. The second term is just a geometric series.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.