Solving recurrence equation with generating functions

Question

$$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?

Answer 1

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.

Answer 2

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?