<s>[INST] 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?
 [/INST] $$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$$
</s>