# 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. – J. M. 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

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]$.

-

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

Since presumably the homework was long due, tackle this with generating functions. I'll use proper subscripts in what follows. Define $H(z) = \sum_{n \ge 0} h_n z^n$. Write the recurrence as: $$h_{n + 2} = 4 h_{n + 1} - 4 h_n + 3 n + 7$$ Multiply by $z^n$, sum over $n \ge 0$, and recognize: \begin{align} \sum_{n \ge 0} h_{n + 1} z^n &= \frac{H(z) - h_0}{z} \\ \sum_{n \ge 0} h_{n + 2} z^n &= \frac{H(z) - h_0 - h_1 z}{z^2} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} to get: $$\frac{H(z) - h_0 - h_1 z}{z^2} = 4 \frac{H(z) - h_0}{z} - 4 H(z) + \frac{3 z}{(1 - z)^2} + \frac{7}{1 - z}$$ Solving for $H(z)$ gives the forbidding expression: \begin{align} H(z) &= \frac{h_0 + (h_1 - 6 h_0) z - (2 h_1 - 9 h_0 - 7) z^2 + (h_1 - 4 h_0 - 4) z^3} {1 - 6 z + 13 z^2 - 12 z^3 + 4 z^4} \\ &= \frac{10}{1 - z} + \frac{3}{(1 - z)^2} - \frac{h_1 - 4 h_0 + 36}{2 (1 - 2 z)} + \frac{h_1 - 2 h_0 + 10}{2 (1 - 2 z)^2} \end{align} Using the generalized binomial theorem and geometric series, this tells us the coefficients: \begin{align} h_n &= 10 + 3 \cdot (-1)^n \binom{-2}{n} - \frac{h_1 - 4 h_0 + 36}{2} \cdot 2^n + \frac{h_1 - 2 h_0 + 10}{2} \cdot \binom{-2}{n} (-2)^n \end{align} As $(-1)^n \binom{-2}{n} = n + 1$, this reduces to: $$h_n = \frac{1}{2} \left( (h_1 - 2 h_0 + 10) n + 2 h_0 - 26) 2^n + 6 n + 26 \right)$$ The algebra help from maxima is gratefully acknowledged.

-