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?
 A: 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.
A: $$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$$
A: 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$.
A: 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)
$$
A: Let $f_p = A + Bn + Cn^2$.
$$
\begin{cases}
2f(n) = 2A +2Bn + 2Cn^2\\
-f(n+1) = -A - B(n+1) - C(n+1)^2\\
-f(n-1) = -A - B(n-1) - C(n-1)^2
\end{cases}
\quad \Rightarrow
$$
$$
3 = Cn^2 - C(2n^2 + 2) = -2C \quad \Rightarrow \quad C = -\frac{3}{2}
$$
Thus, 
$$
f(n) = C_1 + C_2n -\dfrac{3n^2}{2}
$$
Now use the given initial conditions to find the constants $C_1$ and $C_2$.
