# Solving recurrence equation with generating functions

$$a_{0}=0$$ $$a_{1}=0$$ $$a_{2}=-1$$ $$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_{n}=n$$

It's just that...I don't know what to do if there are $a_{n+1}$ instead of $a_{n-1}$, I don't know what to do with that $n$...How can I solve this?

-
If you want negative indices, transform $n+3 \to n$ and you'll get $a_n - 6a_{n-1} + 12a_{n-2} - 8a_{n-3} = n-3$, $n \ge 3$. – Daniel R Aug 12 '13 at 11:49
Try increasing n by 1 and taking the difference of the resulting equations, you get the recurrence relation: $$a_{n+4}-7a_{n+3}+18a_{n+2}-20a_{n+1}+8a_n=1.$$ Now try finding a homogenous solution and a particular solution and add those together to get a general solution. – walcher Aug 12 '13 at 12:13
@walcher, in the first place, I think that's the hard way, and in the second place, I don't think it engages with OP's discomfort with $a_{n+1}$. – Gerry Myerson Aug 12 '13 at 12:28
I think I do not understand the exact nature of the discomfort @GerryMyerson is mentioning. OP: you might want to clarify "what to do if there are $a_{n+1}$ instead of $a_{n−1}$", perhaps by giving a case you can solve. – Did Aug 12 '13 at 13:52
@Did, my impression is that OP has a recipe for solving equations like $a_n-6a_{n-1}+12a_{n-2}-8a_{n-3}=n$ and doesn't understand how to twiddle the recipe to deal with the equation actually given. – Gerry Myerson Aug 13 '13 at 0:10

We are given $$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_n=n.$$ Increasing $n$ by one gives us $$a_{n+4}-6a_{n+3}+12a_{n+2}-8a_{n+1}=n+1.$$ Subtracting these two equations yields $$a_{n+4}-7a_{n+3}+18a_{n+2}-20a_{n+1}+8a_n=1,$$ so we will focus on solving this recurrence relation. First we find the general homogenous solution, i.e. the general solution to $$a_{n+4}-7a_{n+3}+18a_{n+2}-20a_{n+1}+8a_n=0.$$ This is a linear recurrence with characteristic equation $$x^4-7x^3+18x^2-20x+8=(x-2)^3(x-1)=0,$$ which we know to have the general solution $a_n=2^n(n^2+an+b)+c$. To find a particular solution we first note that $n-6n+12n-8n=-n$, so make the Ansatz $a_n=-n+d$. Substituting into $$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_n=n$$ gives an equation for $d$, which is solved by $d=-3$, so our general solution is $$a_n=a_n=2^n(n^2+an+b)+c-n-3.$$ Substitute the three initial conditions and solve for $a$, $b$ and $c$ to get the solution.

-
This does not address the question: it deals neither with the specific issue (what to do with indices greater than $n$) nor with the desired method of solution (via generating functions). – Brian M. Scott Aug 12 '13 at 13:24
Moreover, the method of finding general and particular solutions can be applied to the original equation, without the increasing-$n$-and-subtracting step. Or, if you're going to do that step, why not do it twice, and get to a homogeneous equation, and forget about particular solutions? – Gerry Myerson Aug 13 '13 at 0:13

Let $f(x) =\sum_{n=0}^{\infty} a_n x^n$. Usually relations like

$$a_{n+3}-6a_{n+2}+12a_{n+1}-8a_{n}=n$$

come with a restriction on n. I'm going to assume the equation holds for all $n \ge 0$.

Multiply by $x^n$:

$$a_{n+3} x^n-6a_{n+2}x^n+12a_{n+1}x^n-8a_{n}x^n=n x^n$$

Sum over $n= 0, 1, 2, \dots$:

$$\sum_{n=0}^{\infty} a_{n+3} x^n-6\sum_{n=0}^{\infty} a_{n+2}x^n+12\sum_{n=0}^{\infty} a_{n+1}x^n-8\sum_{n=0}^{\infty} a_{n}x^n=\sum_{n=0}^{\infty} n x^n$$

To deal with a sum like $\sum_{n=0}^{\infty} a_{n+1} x^n$, for example, observe that

$$x \sum_{n=0}^{\infty} a_{n+1} x^n = \sum_{n=0}^{\infty} a_{n+1} x^{n+1}= \sum_{n=1}^{\infty} a_n x^n = f(x) - a_0$$ so $$\sum_{n=0}^{\infty} a_{n+1} x^n = \frac{f(x)-a_0}{x}$$

Maybe you can handle the rest?

-