Recurrence of the form $2f(n) = f(n+1)+f(n-1)+3$

Can anyone suggest a shortcut to solving recurrences of the form, for example:

$2f(n) = f(n+1)+f(n-1)+3$, with $f(1)=f(-1)=0$

Sure, the homogenous solution can be solved by looking at the characteristic polynomial $r^2-2x+1$, so that in general a solution for the homogenous equation is of the form $f^h(n) = c_1+c_2n$. But how does one deal with the constant 3 in this case?

Solution 1:

A related problem: (I). Here is a another way to do it. Rearranging the equation gives

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

$$\implies \sum_{n=0}^{n-2}(f(i+2)-f(i+1))- \sum_{n=0}^{n-2}(f(i+1)-f(i))=-3\sum_{i=0}^{n-2}1 $$

$$ \implies (f(n)-f(1)) - ( f(n-1) - f(0) ) = -3 (n-1) . $$

Applying the initial conditions gives

$$ \implies f(n)-f(n-1) = -3(n-1)\longrightarrow (*) .$$

We repeat the above techniques (telescoping summing) on $(*)$ yields

$$ \sum_{i=1}^{n}(f(i)-f(i-1)) = -3\sum_{i=1}^{n}(i-1)=\dots. $$

I think you can finish it.

Solution 2:

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

$$ \begin{bmatrix} f(n+1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n) \\ f(n - 1) \end{bmatrix} + \begin{bmatrix} -3 \\ 0 \end{bmatrix} $$

$$ \begin{bmatrix} f(n+1) \\ f(n) \\ 1 \end{bmatrix} = \begin{bmatrix} 2 & -1 & -3 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} f(n) \\ f(n - 1) \\ 1 \end{bmatrix} $$

$$ \begin{bmatrix} f(n+1) \\ f(n) \\ 1 \end{bmatrix} = \begin{bmatrix} 2 & -1 & -3 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{bmatrix}^n \begin{bmatrix} f(1) \\ f(0) \\ 1 \end{bmatrix} $$

And if that form isn't closed enough for you, Jordan Decomposition:

$$\begin{align} \begin{bmatrix} f(n+1) \\ f(n) \\ 1 \end{bmatrix} &= \left(\begin{bmatrix} -3 & -3 & 0 \\ -3 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} -3 & -3 & 0 \\ -3 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{-1}\right)^n \begin{bmatrix} f(1) \\ f(0) \\ 1 \end{bmatrix} \\ & = \begin{bmatrix} -3 & -3 & 0 \\ -3 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix}^n \begin{bmatrix} -3 & -3 & 0 \\ -3 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{-1} \begin{bmatrix} f(1) \\ f(0) \\ 1 \end{bmatrix} \\ & = \begin{bmatrix} -3 & -3 & 0 \\ -3 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & n & \frac{n(n-1)}2 \\ 0 & 1 & n \\ 0 & 0 & 1\end{bmatrix} \begin{bmatrix} -3 & -3 & 0 \\ -3 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{-1} \begin{bmatrix} f(1) \\ f(0) \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} n+1 & -n & \frac{-3n^2 - 3n}2 \\ n & 1 - n & \frac{-3n^2 + 3n}2 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} f(1) \\ f(0) \\ 1 \end{bmatrix} \end{align}$$

$$f(n) = n\,f(1) + (1-n)\,f(0)+ \frac{-3n^2 + 3n}2$$

Solution 3:

Just as you would do in the continuous case, where your equation is $f''=-3$. Plug in $f_p=c_3 n^2$. Then $-f_p(n+1)+2 f_p(n)-f_p(n-1)=-2 c_3$. Therefore use $c_3=-3/2$. Then your general solution is $f_g=c_1+c_2 n-3n^2/2$.

Solution 4:

we can use the generating function $F(x)=\sum_{k=1}^{\infty} f(k)x^k$

the recurrence relation may be written: $$2f(n+1) = f(n+2)+f(n)+3$$ so multiplying by $x^{n+2}$ we have $$2xf(n+1)x^{n+1} = f(n+2)x^{n+2}+x^2f(n)x^n+3x^{n+2}$$ and summing for $n=0$ to $\infty$ $$ 2x(F(x)-f(0)) = F(x)-xf(1)-f(0) + x^2F(x) +3x^2(1-x)^{-1} $$ since $f(1)=0$ and $f(0)=\frac32$ this gives (writing $F$ for $F(x)$) $$ -(1-x)^2F= 3x - \frac32 +3x^2(1-x)^{-1}= \frac32(2x-1 +2x^2(1-x)^{-1})=\frac32(3x-1)(1-x)^{-1} $$ so $$ F(x)=-\frac32(3x-1)(1-x)^{-3} $$thus for $n \ge 1$ we have $f(n)$, the coefficient of $x^n$ is $-\frac32 \left(3 \binom{n+1}2 - \binom{n+2}2 \right)$ which simplifies to $$ f(n) = -\frac32 (n^2-1) $$