Trying to solve non-homogeneous linear recurrence relation with difficult non-homogeneous part 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!
 A: $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.
A: 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.
A: 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.
