2

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!

tyler.dunn
  • 21
  • 1
    Looking at the homogeneous recurrence, you have root $1$ which implies a part of the solution will look like $A\cdot 1^n$. A second root $1$ implies that the second part of the solution will look like $B\cdot n\cdot 1^n$ (i.e. $A+Bn$). Now... looking at the homogeneous part, it is a constant times $1^n$ (difficult to see since $1^n$ is invisible). Since this would imply a third part of the solution looking like $1^n$ but we already have one piece as $1^n$ and another piece as $n\cdot 1^n$... we need to use $C\cdot n^2\cdot 1^n$. – JMoravitz Jul 15 '16 at 22:30
  • The number of times a specific part of a solution is attempted to be repeated, you need to multiply it by $n$ enough times to make it distinct from the previous occurrences. The same would be true if it were $2^n$'s trying to be repeated. $f(n)=4f(n-1)-4f(n-2)+2^n$ would have parts $A2^n + Bn2^n$ for the homogeneous part, and due to overlap $Cn^22^n$ for the nonhomogeneous part. – JMoravitz Jul 15 '16 at 22:33
  • this is a convolution equation : $(\delta_0 + 2 \delta_2 - 2\delta_1) \ast f = 2$. So we need to find the inverse filter $h(n)$ such that $h \ast (\delta_0 + 2 \delta_2 - 2\delta_1) = \delta$, i.e solve the homogeneous equation with initial condition $h(0) =1$. and then the solution is $f = h \ast (\delta_0 + 2 \delta_2 - 2\delta_1) \ast f = h \ast 2$. @JMoravitz – reuns Jul 15 '16 at 22:34
  • So @JMoravitz, do I have to treat the non-homogeneous part as a polynomial like $Cn^2+Dn+E$? I'll try that now and see if I can get that to work. – tyler.dunn Jul 15 '16 at 22:51
  • @tyler.dunn $+Dn+E$ is unnecessary and will cancel (as you already saw happen). – JMoravitz Jul 16 '16 at 00:34

3 Answers3

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.

JMoravitz
  • 79,518
0

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.

Claude Leibovici
  • 260,315
0

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.

bof
  • 78,265