How to solve 3rd order nonhomogeneous recurrence relation with n in equation?

This is a homework question so specifically I am looking for a direction (help). Not an absolute answer.

I understand how to solve 2nd order nonhomogeneous (and I think 3rd order is similiar) recurrence relations. Whats kinking me up with this one is a term with n.

h[n] = 4h[n- 1] - 4h[n-2] + 3n + 1


Here I am using square brackets to indicate subscripts. Now I can reorganize this equation into:

0 = h[n] - 4h[n-1] + 4h[n-2] -3n-1


From which I can derive the characteristic equation:

0 = x^3 - 4x^2 + 4x - 3n -1


Normally at this point I would solve the roots and be on my way, but here I have that extra n. How do I deal with this?

-
Try $g_n = h_n - 3n$. And try if this can take you further. –  user17762 Nov 11 '10 at 3:36
Have you seen this? Indeed, normally one starts deriving solutions to inhomogeneous recurrences from solutions to the corresponding homogeneous ones. –  Ｊ. Ｍ. Nov 11 '10 at 3:39
Your characteristic equation is all wrong; it should be just $0=x^2-4x+4$. The terms $3n+1$ are taken care of by finding a particular solution. (PS. Your recurrence is of second order, not third, since each $h_n$ depends on the two previous values $h_{n-1}$ and $h_{n-2}$.) –  Hans Lundmark Nov 11 '10 at 7:09
add comment

2 Answers

Your 'characteristic equation' doesn't work, as you noted, because of the presence of the variable $n$; it leaves the equation making no sense. While the particular-solution method works well, there's another general technique that can be used (in principle) to solve recurrence relations that are linear in previous terms and polynomial in $n$: generating functions. Consider the generating function $H(x) = \sum_{n=0}^{\infty} h[n]x^n$ and use your equation for $h[n]$ to come up with a corresponding equation for $H(x)$. Note that the generating function for $h[n-1]$ is simply $xH(x)$; the 'generating function' for a constant $c$ is $c\over 1-x$, and the generating function for $n$ is $x\over(1-x)^2$ (as can be found by taking the derivative of the generating function for 1 and multiplying by $x$). Once you come up with a formula you can use it to solve for $H(x)$ and then use the usual partial-fraction methods to turn this back into an explicit formula for $h[n]$.

-
add comment

HINT $\$ Find a particular polynomial solution $\rm\:h[n]\:$ by undetermined coefficients (notice that the degree can be at most 1).$\$ The general solution is then the sum of any particular solution and the general solution of the associated homogeneous equation $\rm\ h[n] -4\ h[n-1] + 4\ h[n-2]\ =\ 0\:$.

-
Do you mean degree two? 4h[n-2] => 4; h[n-1] => x; h[n] => x^2? –  Joshua Enfield Nov 11 '10 at 4:26
No. If h(n) = a_k n^k + ... a_1 n + a_0 then h[n] - 4 h[n-1] + 4 h[n-2] = 3 n + 1 implies that k = 1 by examining leading terms. –  Bill Dubuque Nov 11 '10 at 4:38
add comment