# Closed form solution of this second order linear difference equation?

$$y(k + 2) - 3y(k + 1) +2y(k) = 2^k + k$$

### Transform into a system of $n$ first order equations (Step 1)

\begin{align} x_1(k) &= y(k)\\ x_2(k) &= y(k + 1) \end{align}

It follows that the second order difference equation becomes the system:

\begin{align} x_1(k+1) &= x_2(k)\\ x_2(k+1) &= -2x_1(k) +3x_2(k) + 2^k + k \end{align}

To put it in matrix form $x(k+1) = Ax(k) + bu(k)$: $$x(k+1) = \begin{bmatrix}0 & 1\\ -2 & 3\end{bmatrix}x(k) + \begin{bmatrix}0 \\1\end{bmatrix} (2^k + k)$$

### Diagonal form (or Jordan canonical form) of $A$ (Step 2)

Characteristic polynomial of the matrix $A$, along with eigenvalues $\lambda_i$ and the corresponding eigenvectors $e_i$:

$$p(\lambda) = \lambda^2 - 3\lambda + 2\\ \lambda_1 = 1, e_1 = \begin{bmatrix}1\\1\end{bmatrix}\\ \lambda_2 = 2, e_2 = \begin{bmatrix}\frac 12\\1\end{bmatrix}\\$$

Matrix $A$ is diagonalizable, that is: $\Lambda = S^{-1}AS$ or $A = S\Lambda S^{-1}$, and it follows that $A^k = S\Lambda^k S^{-1}$

$$A^k = \begin{bmatrix}1 & \frac 12\\ 1 & 1\end{bmatrix} \begin{bmatrix}1 & \\ & 2^k\end{bmatrix} \begin{bmatrix}2 & -1\\-2 & 2\end{bmatrix} = \begin{bmatrix}2-2^k & 2^k -1 \\ 2 -2^{k+1} & 2^{k+1} - 1\end{bmatrix}$$

This is right because $S\Lambda^0 S^{-1} = I$ and $S\Lambda^1 S^{-1} = A$

### Closed form solution (Step 3)

I know that the general solution of a discrete dynamic system is:

\begin{align} x(1) &= Ax(0) + bu(0)\\ x(2) &= Ax(1) + bu(1)\\ & = A(Ax(0) + bu(0)) + bu(1)\\ &= A^2x(0) + Abu(0) + bu(1)\\ x(3) &= Ax(2) + bu(2)\\ &= A(A^2x(0) + Abu(0) + bu(1)) + bu(2)\\ &= A^3x(0) + A^2bu(0) + Abu(1) + bu(2)\\ x(k) &= A^kx(0) + \sum_{i = 0}^{k-1}A^{k-1-i}bu(k) \end{align}

Because $y(k) = x_1(k)$ we only need the first row of $A^k$, that is $A_1^k$. The solution for the homogeneous equation is:

$$y_h(k) = (2 - 2^k)y(0) + (2^k - 1)y(1)$$

How to find the closed form for the particular solution?

-
See a related technique. –  Mhenni Benghorbal Mar 25 '14 at 18:14
Note that $x^2-3x+2 = (x-1)(x-2)$. –  marty cohen Mar 23 at 3:29

One way to find the particular solution is to use the method of undetermined coefficients. Just as in the case of differential equations, this involves guessing suitable terms to add to $y(k)$ which will generate the correct terms on the right-hand side of the equation.
Let $L$ be the linear operator on sequences defined by $$(Ly)(k) = y(k+2)-3y(k+1)+2y(k),$$ so that the difference equation becomes $$(Ly)(k) = 2^k+k.$$ A natural guess for a sequence $y(k)$ which will produce $(Ly)(k)=2^k$ is $y(k)= B 2^k$, for a constant $B$. However, this sequence is a solution to the homogeneous equation, so you get $(Ly)(k)=0$. This can be fixed by multiplying by a power of $k$. In this problem, since the eigenvalue $\lambda=2$ of $A$ has multiplicity $1$, multiplying by $k^1=k$ works, so you can try $y(k)=B k 2^k$. Similarly, the sequence $y(k)=Ck+D$ might produce $(Ly)(k)=k$, but since $y(k)=1$ solves the homogeneous equation, you will get $(Ly)(k)=E$ for some constant $E$. Again, since the eigenvalue $\lambda=1$ of $A$ has multiplicity $1$, multiplying by $k^1=k$ solves the problem: you can try $y(k)=Ck^2+Dk$. Putting these terms together, there will be a particular solution of the form $$y(k)=Bk2^k+Ck^2+Dk,$$ for some constants $B$, $C$, and $D$. Now, solve for $B$, $C$, and $D$.
Use generating functions directly. Define $g(z) = \sum_{n \ge 0} y(n) z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$, recognize the resulting sums: \begin{align} \sum_{n \ge 0} y(n + r) z^n &= \frac{g(z) - y(0) - y(1) z - \ldots - y(r - 1) z^{r - 1}}{z^r} \\ \sum_{n \ge 0} 2^k z^k &= \frac{1}{1 - 2 z} \\ \sum_{n \ge 0} k z^k &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \end{align} to get: $$\frac{g(z) - y(0) - y(1) z}{z^2} - 3 \frac{g(z) - y(0)}{z} + 2 g(z) = \frac{1}{1 - 2 z} + \frac{z}{(1 - z)^2}$$ Solve for $g(z)$, express as partial fractions: $$g(z) = \frac{2 y(1) - 2 y(0) - 1}{2 (1 - 2 z)} + \frac{1}{2 (1 - 2 z)^2} - \frac{y(1) - 2 y(0)}{1 - z} + \frac{1}{(1 - z)^2} - \frac{1}{(1 - z)^3}$$ Now use the generalized binomial theorem to read off the coefficients: $$(1 + u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} u^k = \sum_{k \ge 0} \binom{m + k - 1}{m - 1} (-1)^k u^k$$ Note that: $$\binom{m + k - 1}{m - 1} = \frac{(m + k - 1) (m + k - 2) \ldots (k + 1)}{(m - 1)!}$$ is a polynomial in $k$ of degree $m - 1$.