# How do I solve for the recurrence relation when P does not exist?

I'm using the method that my textbook uses. I first put the recurrence relation in the form of a matrix. After that I solve for the eigenvalues and eigenspaces to find P. Then they use P to find D and finally plug everything into $A^k = PD^kP^{-1}$ I did this for a problem before and got the correct answer, but not I'm stuck. I have an eigenvalue with algebraic multiplicity of 2 but an eigenspace of 1. So, P does not exist.

The problem is: $y_1$ = 1, $y_2$ = 6, $Y_n = 4Y_{n-1} - 4Y_{n-2}$ for $n \ge 3$

$$A = \begin{bmatrix} 4 & -4 \\ 1 & 0 \\ \end{bmatrix}$$

I find that the eigenvalue is $(\lambda - 2)^2$ = 0 so $\lambda$ = 2

Finally I solve for the eigenspace and get $E_2$ = span $\begin{bmatrix} 2 \\ 1 \\ \end{bmatrix}$

Am I making a mistake?

• Not only $P$ does not exist, neither does $D$. But you can make it similar to a upper triangular matrix $T$. It's not a diagonal matrix, but its still simple to finds its powers. – Git Gud Oct 27 '14 at 1:57
• Can you please show me how? – Ayoshna Oct 27 '14 at 2:01
• There are basically two typical ways to go about this. One is to find the Jordan Normal Form of $A$, the other is to triangularize $A$. Any complex matrix is triangularizable (in other words, similar to a triangular matrix, usually upper triangular is chosen). In this answer I explain with a $3\times 3$ example how to triangularize a matrix. – Git Gud Oct 27 '14 at 2:19
• But if this problem was presented to you, then most likely you were taught one of these methods and you should use it. If you weren't taught any of this, I suppose the best thing to do is to compute a few powers of $A$ directly and try to find a pattern. the solution is $A^n=\begin{bmatrix} 2^n(n+1) & -2^{n+1}n\\ 2^{n-1}n& -2^n(n-1)\end{bmatrix}$, for all $n\in \mathbb N$. You can always take a vector $v$ such that $\left\{\begin{bmatrix} 2 \\ 1\end{bmatrix}, v\right\}$is alinearly independent set. This will always make $P^{-1}AP$ upper triangular. – Git Gud Oct 27 '14 at 2:24
• If no one answers your question, it would be nice if you gave an answer so this doesn't come up as unanswered. – Git Gud Oct 27 '14 at 10:16

As an alternative to linear algebra, we can proceed via generating functions. Let $Y(x):=\sum_{n=1}^\infty y_n x^n$ with $\{y_n\}$ the sequence defined in the question. Then we may write
\begin{align} Y(x) &=y_1x+y_2x^2+ \sum_{n=3}^\infty y_n x^n\\ &=x+6x^2+\sum_{n=3}^\infty (4y_{n-1}-4y_{n-2}) x^n\\ &=x+6x^2+4x\sum_{n=2}^\infty y_{n} x^n-4x^2\sum_{n=1}^\infty y_{n} x^n \\ &=x+6x+4x(Y(x)-1)-4x^2Y(x) \end{align} where in the second line we have used the recurrence relation. Solving for $Y(x)$ then gives $$Y(x)=\dfrac{x+2x^2}{1-4x+4x^2}=\dfrac{x(1-2x)+4x^2}{(1-2x)^2}=\dfrac{x}{1-2x}+\frac{4x^2}{(1-2x)^2}.$$
Since the coefficients of $Y(x)$ are the sequence $\{y_n\}$, all that remains is to expand both terms in a Taylor series and identify coefficients on both sides.
There's a few ways to do this; I'll do so by writing the generating function using derivatives as $Y(x)=x\left(1-2x\dfrac{d}{dx}\right)\dfrac{1}{1-2x}$. Since $\dfrac{1}{1-2x}=\sum_{n=0}^\infty (2x)^n$ is a geometric series, we can differentiate term-by-term. A little algebra then gives $Y(x)=x+\sum\limits_{n=2}^\infty 2^{n-1}(2n-1)x^n$. Hence $y_n=2^{n-1}(2n-1)$ for $n \geq 2$.