Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
See a related technique. –  Mhenni Benghorbal Mar 25 at 18:14
add comment

2 Answers

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

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.