Where is the error in finding the particular solution to this recurrence relation?

Question

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$.

Answer 1

You started with the assumption that there existed two constants $a,b$ such that $y_k = a+bk$ was a solution. After a bit of algebra you end up with
$y_k$ is a solution $\iff \forall k, y_{k+2}-4y_{k+1}+3y_k = -4k \iff \forall k, b = 2k$.
So $b$ has to be equal to every even integer at once. Obviously this is impossible : you have reached a contradiction and there is no solution of the form $a+bk$.

If $z_k = y_{k+2}-4y_{k+1}+3y_k$, then you can check that $z_{k+1}-z_k$ is constant, and then that $z_{k+2}-2z_{k+1}+z_k = 0$. So the solutions to the orignal equation is a subset of the solutions of a larger homogeneous linear recurrent relation. Its characteristic polynomial is $(r-1)^3(r-3)$, so the solutions to this homogeneous equation ends up being $\{y_k = a+bk+ck^2+d3^k \mid (a,b,c,d) \in \Bbb R^4\}$, so you only have to check which of those satisfy the original equation, and obtain the value of $b$ and $c$.

Answer 2

Your error is to put $b=2k$, when $b$ is a constant. Notice that one of the solutions you have to the homogeneous equation is $1^k$. This means that you have to increase the degree of your particular solution and try $a+bk+ck^2$.

Because $1$ is a root of the auxiliary equation, the term in $a$ will simply go to zero (try it). The term in $b$ goes to a constant (as you have computed, in fact) and would help if you had a constant term on the right-hand side, and the term in $c$ will be what you need for the $k$ term. It works like this (you will see that all the leading coefficients cancel):

$$a+b(k+2)+c(k+2)^2-4a-4b(k+1)-4c(k+1)^2+3a+3bk+3ck^2 =$$$$2b+4ck+4c-4b-8ck-4c=-2b-4ck$$ From which you get $b=0, c=1$

Answer 3

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}