2
$\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} (-1)^k \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} u^k $$ and the fact that $\binom{k + m - 1}{m - 1}$ is a polynomial of degree $m - 1$ in $k$ finishes this off.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

If you guess that $a_n = (p_3 n^3 + p_2 n^2 + p_1 n + p_0)2^n$ is a solution for the recurrence, then solve this linear system for $p_3,p_2,p_1,p_0$ in terms of $a_0$ and $a_1$: $$ \begin{eqnarray} a_0 &=& (p_3 0^3 + p_2 0^2 + p_1 0 + p_0) 2^0 \\ a_1 &=& (p_3 1^3 + p_2 1^2 + p_1 1 + p_0) 2^1 \\ a_2 &=& (p_3 2^3 + p_2 2^2 + p_1 2 + p_0) 2^2 \\ a_3 &=& (p_3 3^3 + p_2 3^2 + p_1 3 + p_0) 2^3 \\ a_2 &=& 4 a_1 -4 a_0 + (2+1)2^2 \\ a_3 &=& 4 a_2 -4 a_1 + (3+1)2^3 \\ \end{eqnarray} $$ This gives $$ a_n = \frac16\left( n^3 + 6n^2 + (3a_1 - 6 a_0 -7)n + 6a_0 \right)2^n $$ which you can check is indeed a solution for the recurrence.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

This difference equation is tricky. Denote by $a_n^o$ the solution to the homogeneous part: $a_n^o-4a_{n-1}^o+4a_{n-2}^o=0$. The characteristic polynomial associated to this equation is $p(z)=z^2-4z+4$ and $p$ has two identical roots: $z_1=z_2=2$, so the general solution to the homogeneous equation is $$a_n^o = (p+qn)2^n.$$ Unfortunately the forcing term in the inhomogeneous equation is exactly of the kind $(p+qn)2^n$, so we have to look for a solution of the kind $a_n=(sn^3+rn^2+qn+p)2^n$. In fact we can neglect the term $(qn+p)2^n$, since it solves the homogeneous equation. Now we put the ansatz $a_n=(sn^3+rn^2)2^n$ in the original inhomogeneous equation: $$L_n=a_n-4a_{n-1}+4a_{n-2}=(sn^3+rn^2)2^n-4(s(n-1)^3+r(n-1)^2)2^{n-1}+4(s(n-2)^3+r(n-2)^2)2^{n-2};$$ eventually we can determine the unknown coefficients $r$,$s$ by forcing $L_n$ to be equal to $(n+1)2^n$. We get $L_n=[s(6n-6)+2r]2^n=(n+1)2^n$, hence $6s=1$ and $-6s+2r=1$ which yield $s=\frac{1}{6}$ and $r=1$.

| cite | improve this answer | |
$\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.