# How to *really* solve a non-homogeneous recurrence

First let me state that I am not asking about the usual procedure for finding a trial solution to a non-homogeneous recurrence. I have been doing this for many years and can solve all the basic types, but I am looking for some deeper insight.

Here are a few examples to serve as a basis for the discussion.

1. For $a_n-a_{n-1}-6a_{n-2}=n^2$ we guess $a_n=cn^2+dn+e$. Why not just $cn^2$? If you want to say "because $(n-1)^2$ contains lower order terms" please read the rest of the question before posting that answer.

2. For $a_n-a_{n-1}-6a_{n-2}=2^n$ we guess $a_n=c2^n$: no further terms as in the previous example.

3. For $a_n-a_{n-1}-6a_{n-2}=3^n$ we guess $a_n=cn3^n$. Why not just $c3^n$? (And again, I do not want the answer "because $3^n$ satisfies the homogeneous recurrence", I know that already.) Why is it not necessary to include a term $dn^23^n$?

4. For $a_n-a_{n-1}-6a_{n-2}=2^n+3^n$ we guess $a_n=c2^n+dn3^n$. How do we really know that $c2^n$ is OK but $d3^n$ is not?

5. For $a_n-6a_{n-1}+9a_{n-2}=n3^n$ we guess $a_n=cn^33^n+dn^23^n$. As above, how do we know in advance that we will not need a term $en^43^n$?

My thoughts on this are very vague, any insight (perhaps even proofs) would be greatly appreciated.

I feel that the answer must have something to do with linear independence in the vector space $V$ of all (let's say real) sequences $\{a_0,a_1,\ldots\}$.

In case 5, for example, if we start with the homogeneous solutions, we have to continue the set $$\{3^n,\,n3^n,\ldots\}$$ until we get four independent sequences - but why four?

In case 4, I assume that we treat the two summands separately because the sequences $\{2^n\}$ and $\{3^n\}$ are linearly independent.

On the other hand, $\{n\}$ and $\{n^2\}$ are also linearly independent and this would be different. For this reason, and also to account for example 1, I suspect that we also need to consider the finite difference operator $$S:\{a_0,a_1,\ldots\}\mapsto\{a_1-a_0,a_2-a_1,\ldots\}\ ,$$ which is a linear transformation on $V$, and perhaps to consider whether $a_n,\,S(a_n),\,S^2(a_n),\ldots$ are linearly independent.

What I would like to see is a theorem of the following shape.

If the $k$th order linear recurrence with constant coefficients $$a_n+\cdots+c_ka_{n-k}=0$$ has solutions ${\rm span}({\bf h}_1,\ldots,{\bf h}_k)$, then the recurrence $$a_n+\cdots+c_ka_{n-k}=f(n)$$ has solutions of the form $a_n={}????$

Any ideas will be read with interest! - but once again, please do not tell me how to solve recurrences! I know how, I am trying to understand why.

-
Are you familiar with the generating functions approach to solving these recurrence relations? I'm under the impression that these guesses for your recurrences come from experience with what comes out of ad hoc or generating function methods. Every case you mentioned is dealt simply by generating functions without any guessing, so if you study the process of solving via generating functions you may be able to see why you make these guesses. – Ragib Zaman May 23 '14 at 5:43
@RagibZaman I can certainly do all this by generating functions. But to me that is just another "how", not a "why". However, if anyone can use generating functions to throw some light on what I have asked, I certainly have no objection. – David May 23 '14 at 6:00

My suggestion is to think of the undetermined coefficient method for linear non-homogeneous ODE, which can be found in any elementary ODE book. Let me illustrate. Let say we want to find a particular solution of $$ay''+by'+cy=f(x),$$ where $a,b,c$ are constants. If $f(x)=x^3$, you will need to plug in a polynomial of degree 3 (try it and see why you need the lower degree terms). Now, if $f(x)=e^{ax}$, then you will need to plug in $y=Ke^{ax}$. I believe it is obvious that you do not need any other terms. Notice that if $f(x)=2^x$, it is a particular case of an exponential since $f(x)=2^x=e^{\ln{(2)} x}$. Now, the only exceptions to those rules if if $f(x)$ is a solution to the homogeneous problem. For example in the case of $$y''-y=e^x.$$ In this case, $y=ke^x$ does not work. You need to pre-multiply by $x$ to try $y=kxe^x$. In general, if $f(x)$ is a solution of the homogeneous problem, you need to pre-multiply the ansatz's I suggested above by $x$. All these results are formulated in theorems in any decent elementary ODE book (for example, the one written by Nagle and Saff). But I think these rules can be understood quite easily by working out simple examples. Note that in relation to your example $n3^n$, I can add the rule that if $f(x)=x^2 e^{ax}$ and that $e^{ax}$ is not a solution of the homogeneous problem, you need to try a polynomial of degree $3$ times $e^{ax}$. Note that if you try to add a term like $x^4e^{ax}$ to your solution, then this term will automatically produce a term proportional to $x^4e^{ax}$, which is unwanted.

If $e^{ax}$ was a solution, then you would need to pre-multiply by $x$. You would try $y=x(bx^3+cx^2+dx+f)e^{ax}$. Again, all this are in the theorems. Now, if $a$ was a double root of the characteristic equation, you would need to pre-multiply by $x^2$ instead. For example $$y''-6y'+9y=x^2e^{3x}.$$ You would try $y=x^2(ax^2+bx+c)e^{3x}.$

Note that in the case of $n3^n$ you mention, the characteristic polynomial has a double root $3$, thus the homogeneous problem has $3^n$ and $n3^n$ as solutions, that is why you need to pre-multiply by $n^2$ and try $n^2(an+b)3^n$,

All what I said I believe extends to your difference equations. Your difference equations are like'' second order differential equation with inhomogeneities made of exponentials and polynomials. So, the rules for the undetermined coefficient method do extend.

-
Hi Stephane, thanks for taking the trouble to answer but I'm afraid it really doesn't address my issues. I know how to solve all these things, I can do them all instantly and I never make a mistake ;-) but it is rather mechanical and I don't feel that I have got to the bottom of it all. I feel sure that there is a linear algebra connection. – David Aug 7 '14 at 5:29
@David Perhaps can you look at DanielV answer to this question. – Stephane Aug 7 '14 at 22:49
Thanks for the reference. It certainly suggests that the extra terms come from powers of a matrix. Will continue to think about it until I achieve enlightenment ;-) – David Aug 8 '14 at 2:36

$$a_{k} - a_{k-1} - 6 a_{k-2} = k^2 \tag{1}\\$$ $$a_{k+1}- a_{k} - 6 a_{k-1} = (k+1)^2 \tag{2}\\$$ denote $\Delta a_{k+1} = a_{k+1} -a_k$ and subtract (1) from (2) to get $$\Delta a_{k+1} - \Delta a_{k} - 6 \Delta a_{k-1} = 2k -1 \tag{3}\\$$ Now $$\Delta a_{k+2} - \Delta a_{k+1} - 6 \Delta a_{k} = 2(k+1) -1 \tag{4}\\$$ denote $b_{k+2} = \Delta a_{k+2} - \Delta a_{k+1}$ and subtract (3) from (4) to get

$$\Delta b_{k+2} - \Delta b_{k+1}-6 \Delta b_k = 2$$ Thus you've got rid of the nonhomogenous term on the RHS. Now rewrite the expression as ($V_{k+2} = \Delta b_{k+2} - \Delta b_{k+1})$ $$V_{k+2} = 2 + 6 \Delta b_{k}$$ and use telescoping sums on both sides (sum on $k$). I know this is slower than the approach you've suggested, but at least it doesn't involve guessing.

-
Thanks for the contribution but it doesn't really answer my question. I agree that your solution doesn't involve guessing, but I don't have any problem with guessing because I always guess right ;-) What I want is to understand the "why" - to have a theorem something like what I have outlined. I feel sure there is a linear algebra connection here somewhere. – David May 23 '14 at 7:36

Shift indices to write the recurrence as:

$$a_{n + 2} - a_{n + 1} - 6 a_n = n^2 + 4 n + 4$$

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$. Recognize some sums to get:

$$\frac{A(z) - a_0 - a_1 z}{z^2} - \frac{A(z) - a_0}{z} - 6 A(z) = \sum_{n \ge 0} n^2 z^n + 4 \sum_{n \ge 0} n z^n + 4 \sum_{n \ge 0} z^n$$

The tricky part here are the sums on the left hand side. But you see that multiplying the coefficient of a series $\sum_{n \ge 0} c_n z^n$ by $n$ results from differentiating and multiplying by $z$ to restore the power "lost" to the derivative. So:

\begin{align} \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} \\ \sum_{n \ge 0} n^2 z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{z}{(1 - z)^2} \\ &= \frac{z}{(1 - z)^2} \\ &= \frac{z + z^2}{(1 - z)^3} \end{align}

Plug all this into the above, and you'll get an algebraic equation for $A(z)$, which gives $A(z)$ as a rational function in $z$ in this case. Split into partial fractions, and remember that:

$$(1 - r z)^{-k} = \sum_{n \ge 0} (-1)^n \binom{-k}{n} r^n z^n = \sum_{n \ge 0} \binom{n + k - 1}{k - 1} r^n z^n$$

This allows you to "read off" the coefficients.

The real fun starts when you have complex roots, which appear in conjugate pairs, call one set of them $\alpha$ and $\overline{\alpha}$, with corresponding terms of the partial fraction expansion (again $\beta$ and $\overline{\beta}$ are complex conjugates):

$$\frac{\beta}{1 - \alpha z} + \frac{\overline{\beta}}{1 - \overline{\alpha} z}$$

This gives rise to a pair of terms in the solution:

$$\beta \cdot \alpha^n + \overline{\beta} \cdot \overline{\alpha}^n$$

This are seen to be the sum of complex conjugates, i.e., this is twice the real part of any of them:

$$2 \Re \left( \beta \cdot \alpha^n \right)$$

Write the numbers is polar form, i.e., $\alpha = \lvert \alpha \rvert \cdot \exp(\arg(\alpha) \mathrm{i})$, which gives:

$$2 \Re \left( \lvert \beta \rvert \exp( \arg(\beta) \mathrm{i} ) \cdot \lvert \alpha \rvert^n \exp( \arg(\alpha) n \mathrm{i}) \right) = 2 \lvert \beta \lvert \cdot \lvert \alpha \rvert^n \cdot \cos(\arg(\alpha) n + \arg(\beta))$$

Repeat complex roots are handled in a similar way, giving terms with binomial coefficients as above.

Much more details are given in Wilf's "generatingfunctionology", at the link you'll find the next to last edition in PDF for free.

-
Thanks for taking the trouble to answer but I'm afraid it really doesn't answer my question. I know how to solve all these things, I can do them by guesswork or generating functions, and I always get the right answer. Well nearly always ;-) But I don't think I really understand why these methods work. I feel sure that there is some kind of linear algebra connection, as in the "wishlist theorem" at the end of my question. – David Aug 11 '15 at 4:56