1
$\begingroup$

I need some help solving the following recurrence relation:

$a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$

What I've tried:

a) Find the general solution of the associated linear homogenous recurrence relation.

I got this general solution : $a^{(H)}_n = \alpha_1*2^n + \alpha_2*n*2^n $

b) Guess the particular solution.

This is the step I'm confused in. Seeing some other examples, I believe a correct guess would be $n^2*(p_1*n + p_0)*2^n$.

To get all the solutions I would have to put this particular solution equation into the original recurrence relation. This way I get a very complex equation. I think either I'm doing this incorrectly or I'm making it too complicated. Is there a better and more intuitive way to solve such recurrence relations?

$\endgroup$
  • $\begingroup$ You are on the right track, and your method should work. There should be a lot of cancellations in your "complex equation" if you do the algebra right. Keep at it! $\endgroup$ – Gerry Myerson May 5 '14 at 12:47
0
$\begingroup$

Use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write the recurrence as: $$ a_{n + 2} = 4 a_{n + 1} - 4 a_n + 4 (n + 3) \cdot 2^n $$ Multiply the recurrence by $z^n$, add over $n \ge 0$, and recognize the sums: \begin{align} \sum_{n \ge 0} a_{n + r} z^n &= \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^r} \\ \sum_{n \ge 0} 2^n z^n &= \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} n \cdot 2^n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\ &= \frac{2 z}{(1 - 2 z)^2} \end{align} Thus: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} - 4 A(z) + 4 \frac{2 z}{(1 - 2 z)^2} + 12 \frac{1}{1 - 2 z} $$ Written as partial fractions: $$ A(z) = \frac{4 + 4 a_0 - a_1}{2 (1 - 2 z)} - \frac{6 + 2 a_0 - a_1}{2 (1 - 2 z)^2} + \frac{1}{(1 - 2 z)^4} $$ Use of the generalized binomial theorem, in particular: $$ (1 + u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} z^k $$ and the fact that $\binom{k + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $k$ finishes this off.

$\endgroup$

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.