3
$\begingroup$

I'm now solving a difference equation,

$$a_{n+2}=4a_{n+1}-4a_{n},a_1=1,a_2=1.$$

to write it in matrix,

$$\left(\begin{matrix}a_{n+2}\\a_{n+1}\end{matrix}\right)=\left(\begin{matrix}4 & -4 \\ 1 & 0 \\\end{matrix}\right)\left(\begin{matrix}a_{n+1}\\ a_{n} \\\end{matrix}\right).$$

then,

$$\left(\begin{matrix}a_{n+1}\\a_{n}\end{matrix}\right)=\left(\begin{matrix}4 & -4 \\ 1 & 0 \\\end{matrix}\right)^{n-1}\left(\begin{matrix}a_{2}\\ a_{1} \\\end{matrix}\right).$$

but how to calculate $\left(\begin{matrix}4 & -4 \\ 1 & 0 \\\end{matrix}\right)^{n-1}$, since it can't be diagonalized.

and i found the answer should be

$a_n=p(n)\cdot2^n$, $p(n)$is polynomial of degree one.

Why? Can some explain this?

$\endgroup$
3
$\begingroup$

For a $2\times2$ matrix $A$, if it is not diagonalisable, it must be similar to a Jordan block, i.e. $A=P(\lambda I+J)P^{-1}$ where $P$ is invertible, $\lambda$ is the repeated eigenvalue of $A$ and $J=\pmatrix{0&1\\ 0&0}$. Since $J^2=0$, \begin{align*} A^n &=P(\lambda I+J)^nP^{-1}\\ &=P(\lambda^nI+n\lambda^{n-1}J)P^{-1}\\ &=P\left[n\lambda^{n-1}(\lambda I+J)-(n-1)\lambda^nI\right]P^{-1}\\ &=n\lambda^{n-1}A-(n-1)\lambda^nI\tag{1} \end{align*} and you may calculate $a_n$ as $a_n=(0,1)\ A^{\color{red}{n-1}} \pmatrix{a_2\\ a_1}$.

Note that $(1)$ works for $2\times2$ matrices only (and it hinges on the fact that $J^2=0$). For larger-sized matrices, their Jordan blocks may have different sizes and hence you should calculate the power blockwise, as suggested by Git Gud's answer. Also, as mentioned in the answer of Clement C., you can solve the linear recurrence directly without turning it into a matrix form.

$\endgroup$
2
$\begingroup$

First, there small typo in the RHS of the first equation (the rightmost vector should have $a_{n+1}$ as first component).

Basically, without using the matrix approach, your recurrence relation has characteristic polynomial $$ P(X) = X^2-4X+4 $$ whose only root (with multiplicity 2) is 2. Hence, a general solution of the recurrence will be of the form $(\alpha n+\beta)2^n$.

$\endgroup$
2
$\begingroup$

Jordan Normal Form, this and this should make it clear.

Regarding the matrix in your problem you get this decomposition.

The above links yield $J^{n-1}=\begin{pmatrix}2^{n-1} & {n-1\choose 1}2^{n-2}\\ 0 & 2^{n-1}\end{pmatrix}$.

Now you can use $M^k=(SJS^{-1})^k=SJ^kS^{-1}$.

$\endgroup$
0
$\begingroup$

There is no need to be that complicated. Here is the trick. an+2=4an+1−4an, then an+2-2an+1=2(an+1-2an). So we can conclude that {an+1-2an} is an geometric progression. (an+1-2an)/(a2-2a1)=2^(n-1), an+1-2an=-2^(n-1), 2an-4an-1=-2^(n-2)*2=-2^(n-1), 4an-1-8an-2=-2^(n-3)*4=-2^(n-1), ....... 2^(n-1)*a2-2^n*a1=-2^(n-1), sum up ,we get an+1-2^n=-n*2^(n-1), so an=2^(n-1)-(n-1)*2^(n-2)=(3/4-n/4)*2^n.

$\endgroup$
1
  • 1
    $\begingroup$ Hello, welcome to Maths.SE. For some basic information about writing maths at this site see e.g. here, here, here and here. $\endgroup$ – Lord_Farin Nov 11 '13 at 14:09

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.