Trying to solve non-homogeneous linear recurrence relation with difficult non-homogeneous part

Question

I have the following recurrence relation that I'm trying to solve:

$$f(n)=2f(n-1)-f(n-2)-2$$

The homogeneous part is easy:

The characteristic polynomial $r^2-2r+r=0$ has root $r=1$ with multiplicity 2, so the general solution is:

$$f(n)=An+B$$

for some initial conditions.

The non-homogeneous part I cannot get. I start with a guess that the solution will be of the form $f(n)=C$ since the $-2$ in the original function is just a constant.

This becomes troublesome, because if $f(n)=C$, $f(n-1)=C$, $f(n-2)=C$, then $f(n)=2f(n-1)-f(n-2)-2$ becomes

$$C=2C-C-2$$ $$0\neq2$$

I get a similar result if I assume a solution of the form $Cn+D$.

What do I need to do here to solve the non-homogeneous part?

Thanks!

Answer 1

$f(n)=2f(n-1)-f(n-2)-2$, $f(0)=f_0$ $f(1)=f_1$

Associated characteristic polynomial for the homogeneous recurrence: $x^2-2x+1=0$ which factors as $(x-1)^2=0$ implying homogeneous part is of the form $An+B$ (one can think of $1^n$'s being present in the same way they would have been had the roots been anything else)

Armed with that knowledge, and since the non-homogeneous part is also a polynomial (in this case of degree zero) which is itself a degenerate case of being of the form $1^n$ as well, we multiply by $n$ enough times to make it distinct from the other already known parts. I.e. we expect the non-homogeneous part to be of the form $C\cdot n^2$. Plugging this into the recurrence, we have:

$Cn^2 = 2C(n-1)^2 - C(n-2)^2 - 2$

$Cn^2 = 2Cn^2 - 4Cn + 2C - Cn^2 +4Cn - 4C - 2$

$2C = -2$

$C=-1$

---

So, we expect $f(n) = An+B-n^2$. Setting $n=0$ we see that $B=f_0$. Setting $n=1$ we see $f_1 = A+f_0-1$ so $A=f_1-f_0+1$ and therefore the final closed form is:

$$f(n) = (f_1-f_0+1)n+f_0-n^2$$

---

Your problem was that you tried using solutions to the non-homogeneous part which overlapped with the solutions to the homogeneous part, which as you saw wound up with statements like $0=-2$ which are impossible. Every solution must be linearly independent from one another, and it so happens that multiplying it by $n$ enough times accomplishes exactly that.

Answer 2

Starting with $$f(n)=2f(n-1)-f(n-2)-2$$ define $f(n)=g(n)+n-n^2$. This gives $$g(n)+n-n^2=2g(n-1)+2(n-1)-2(n-1)^2-g(n-2)-(n-2)+(n-2)^2-2$$ Develop and simplify to get $$g(n)=2g(n-1)-g(n-2)$$ which looks more pleasant.

Answer 3

If you've had an elementary course in differential equations, you can use an exponential generating function to turn this into an easy differential equation.

In terms of the exponential generating function $$y(x)=\sum_{n=0}^\infty\frac{f(n)}{n!}x^n$$ the nonhomogeneous linear recurrence equation $$f(n)=2f(n-1)-f(n-2)+2$$ turns into the nonhomogeneous linear differential equation $$y''-2y'+y=2e^x.$$ Standard methods of elementary differential equations (variation of parameters or the undetermined coefficients or annihilator method) lead to the particular solution $$y_p=x^2e^x$$ and the general solution $$y=c_1e^x+c_2xe^x+x^2e^x$$ where $c_1$ and $c_2$ are arbitrary constants. Thus $$\sum_{n=0}^\infty\frac{f(n)}{n!}x^n=y(x)=\sum_{n=0}^\infty\frac{c_1+c_2n+n(n-1)}{n!}x^n,$$ that is, $$\boxed{f(n)=c_1+c_2n+n(n-1),}$$ the general solution of the recurrence equation.