I am having a hard time understanding these questions. I know I need to find the associated homogeneous recurrence relation first, then its characteristic equation. I cant figure out how to find the particular solution to the non homo recurrence relation though.

Ex: $$a_{n}= 4a_{n-1} + 4a_{n-2} + (n+1)2^n$$

My characteristic equation is $r^2-4r-4=0$ and $r=2(1+ \sqrt{2}), r=2(1- \sqrt{2})$. Next I need to guess some equation for my $f(n)=(n+1)2^n$ and plug it into the original to find some constants,, I am having the trouble here,, I dont understand how to come up with these guess equations.

I know the theorem that says the general solution (of the non homo recurrence relation) is the general solution of the associated recurrence relation + the particular solution: $a_{n}=a_{n}^{(h)} + a_{n}^{(p)}$

So far I have $a_{n}=A2(1+ \sqrt{2})^n + B2(1- \sqrt{2})^n + a_{n}^{(p)}$


Forget all this, use generating functions directly. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write: $$ a_{n + 2} = 4 a_{n + 1} + 4 a_n + 8 (n + 3) \cdot 2^n $$ Multiply by $z^n$, sum over $n \ge 0$, recognize: \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 2^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\ &= \frac{2 z}{(1 - 2 z)^2} \end{align} and get: $$ \frac{A(z) - a_0 - a_1 z}{z^2} = 4 \frac{A(z) - a_0}{z} + 4 A(z) + \frac{16 z}{(1 - 2 z)^2} + \frac{3}{1 - 2 z} $$ This gives, written as partial fractions (partially): $$ A(z) = \frac{1 - 2 a_0 - 2 (a_1 - 1) z}{2 (1 - 2 z^2)} +\frac{1}{2 (1 - 2 z)} $$ The $(1 - 2 z)^{-1}$ gives rise to a $2^n$ in the solution, while you can write: \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} Thus you get expressions for even/odd indices. Or you could split that into partial fractions too, and mess with the resulting irrationals.

If you are simply interested in a particular solution, pick any easy values, like $a_0 = 0$ and $a_1 = 1$, and expand the above.


Make sure you have enough functions to span the non-homogeneous term. In this case, the non-homogeneous term is $n2^n + 2^n$, so I would guess $a_n^{(p)} = An2^n + B2^n$. The reason this is enough is because the space of functions spanned by $\{n2^n, 2^n\}$ is invariant under the next operation, and it intersects the space of homogeneous solutions only at $0$.

  • $\begingroup$ Hmmm, sounds foreign to me,, Is there a general way of finding an^(p)? Do you always just stick a constant to each term and see if you can solve it? $\endgroup$ – htcSpt Jun 21 '13 at 2:15
  • $\begingroup$ There is a general way, by means of generating functions or $Z$ transformation, or variation of parameters. But I would say this method of undetermined coefficients is much simpler in this case. $\endgroup$ – Tunococ Jun 21 '13 at 2:17

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.