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?

  • $\begingroup$ 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. $\endgroup$ – Git Gud Oct 27 '14 at 1:57
  • $\begingroup$ Can you please show me how? $\endgroup$ – Ayoshna Oct 27 '14 at 2:01
  • $\begingroup$ 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. $\endgroup$ – Git Gud Oct 27 '14 at 2:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Git Gud Oct 27 '14 at 2:24
  • $\begingroup$ If no one answers your question, it would be nice if you gave an answer so this doesn't come up as unanswered. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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