Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
Try $g_n = h_n - 3n$. And try if this can take you further. –  user17762 Nov 11 '10 at 3:36
2  
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
1  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

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\:$.

share|improve this answer
    
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
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.