<s>[INST] Where is the error in finding the particular solution to this recurrence relation? The question is to write the general solution for this recurrence relation:
$y_{k+2} - 4y_{k+1} + 3y_{k} = -4k$.
I first solved the homogeneous equation $y_{k+2} - 4y_{k+1} + 3y_{k} = 0$, by writing the auxiliary equation $r^2 - 4r + 3 = (r-3)(r-1) = 0$. Thus $y_k^{h} = c_1(1)^k + c_2 (3)^k$. The general solution is just $y_k^{gen} = y_k^{h} + y_k^{p}$. My trouble is coming up with a particular solution. I keep up coming with $y_k^{p} = 2k^2$ when that doesn't work, but $k^2$ works, so my answer is close. I've gone through the artihmetic several times and cannot spot the mistake, here's the work:
The particular solution is of the form $y_k^{p} = a + bk$. Plugging in recurrence relation: $a + b(k+2) - 4(a + b(k+1) + 3(a + bk) = (a - 4a + 3a) + (bk - 4bk + 3bk) + (2b - 4b) = 0 + 0 - 2b = -4k$.
Thus $b = 2k$, and since our $y_k^p = a + bk$, it doesn't matter what pick $a$ to be so choose $a = 0$, which gives us $y_k^p = 2k^2$.
However, $2k^2$ doesn't satisfy the recurrence relation:
$2(k+2)^2 - 8(k+1)^2 + 6k^2 = (2k^2 - 8k^2 + 6k^2) + (8k - 16k) + (8 - 8) = -8k \ne -4k$.
Where is the error in my reasoning? I know $y_k^p = k^2$ works, but why do I keep coming up with $2k^2$.
 [/INST] As a side remark, it is best to use generating functions and solve the equation in one go. Define $g(z) = \sum_{k \ge 0} y_k z^k$, multiply the recurrence by $z^k$, sum over $k \ge 0$, and recognize a few sums:
\begin{align}
\sum_{k \ge 0} y_{k + r} z^k 
  &= \frac{g(z) - y_0 - y_1 z - \ldots - y_{r - 1} z^{r - 1}}{z^r} \\
\sum_{k \ge 0} k z^k
  &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\
  &= \frac{z}{(1 - z)^2}
\end{align}
and so get:
$$
\frac{g(z) - y_0 -y_1 z}{z^2}
  - 4 \frac{g(z) - y_0}{z}
  + 3 g(z)
  = - 4 \frac{z}{(1 - z)^2}
$$
Written as partial fractions:
$$
g(z) = \frac{1 - y_0 - y_1}{2 (1 - 3 z)}
         + \frac{3 + 3 y_0 - y_1}{2 (1 - z)}
         - \frac{3}{(1 - z)^2}
         + \frac{2}{(1 - z)^3}
$$
Your particular solution comes from the terms that don't include the initial values.
The generalized binomial theorem for negative integer powers gives for them:
\begin{align}
- 3 \binom{-2}{k} (-1)^k + 2 \binom{-3}{k} (-1)^k
  &= -3 \binom{k + 2 - 1}{2 - 1} + 2 \binom{k + 3 - 1}{3 - 1} \\
  &= -3 (n + 1) + 2 \frac{(n + 2) (n + 1)}{2} \\
  &= n^2 - 1
\end{align}
</s>