6
$\begingroup$

I have a matrix $ A = \left[ {\begin{array}{cc} 1 & c \\ 0 & d \\ \end{array} } \right] $

with $c$ and $d$ constant. I need to find $A^n$ ($n$ positive) and then need to prove that formula using induction.

I would like to check that the formula I derived is correct:

$ A^n = \left[ {\begin{array}{cc} 1 & c^{n-2}(dc + c) \\ 0 & d^n \\ \end{array} } \right] $

If this is correct, how can I prove this? I suppose I can write $A^{n+1} = A^n A$, which would be

$ \left[ {\begin{array}{cc} 1 & c^{n-2}(dc + c) \\ 0 & d^n \\ \end{array} } \right] \left[ {\begin{array}{cc} 1 & c \\ 0 & d \\ \end{array} } \right] $

But then what would I do?

Thanks.

  • 0
    Multiplying, I get {{1,d (d c+c) c^(n-2)+c},{0,d^3}}, So the formula I got seems wrong. I know the 1 and 0 on the left are constant, and the d follows d^n, but the upper right one is giving me problems. Suggestions?2011-06-09

4 Answers 4

10

Mathematical induction is the way to go, but first you want to have a "target." I'm not sure what you did, but I think you confused $c$ and $d$ somewhere along the line in your calculations. Let's see a first few values:

$\begin{align*} A&= \left(\begin{array}{cc}1&c\\0&d\end{array}\right)\\ A^2 &= \left(\begin{array}{cc}1&c\\0&d\end{array}\right)\left(\begin{array}{cc}1&c\\0&d\end{array}\right) = \left(\begin{array}{cc}1 & c+cd\\0&d^2\end{array}\right).\\ A^3 &= \left(\begin{array}{cc} 1&c+cd\\ 0 &d^2\end{array}\right) \left(\begin{array}{cc} 1 & c\\ 0 & d\end{array}\right) = \left(\begin{array}{cc} 1 & c+cd+cd^2\\ 0 & d^3 \end{array}\right).\\ A^4 &= \left(\begin{array}{cc} 1&c+cd+cd^2\\ 0 & d^3 \end{array}\right)\left(\begin{array}{cc} 1 & c\\0 & d\end{array}\right) = \left(\begin{array}{cc} 1 & c + cd + cd^2 + cd^3\\ 0 & d^4 \end{array}\right). \end{align*}$ Okay, that suggests the pattern:

Conjecture. For every positive integer $n$, $A^n = \left(\begin{array}{cc} 1 & c(1+d+d^2+\cdots + d^{n-1})\\ 0 & d^n \end{array}\right).$

To prove the conjecture, we use mathematical induction. Prove the formula is true for $n=1$, and then, assuming the formula holds for $k$, prove it holds for $k+1$. We have:

Basis. For $n=1$, we have $A = \left(\begin{array}{cc}1 & c\\0 & d\end{array}\right),$ so the formula holds.

Inductive step. Show that if the formula holds for $k$, then it also holds for $k+1$.

Induction hypothesis. Assume the result holds for $k$; that is, that $A^k = \left(\begin{array}{cc} 1 & c(1+d+\cdots+d^{k-1})\\0 & d^k \end{array}\right).$

Now we have: $\begin{align*} A^{k+1} & = A^kA\\ &= \left(\begin{array}{cc} 1 & c(1+d+\cdots + d^{k-1})\\0 & d^k\end{array}\right) \left(\begin{array}{cc} 1 & c\\0 & d\end{array}\right)\\ &= \left(\begin{array}{cc} 1 & c + cd(1+d+\cdots + d^{k-1})\\ 0 & d^{k+1}\end{array}\right)\\ &= \left(\begin{array}{cc} 1 & c(1 + d(1+d+\cdots + d^{k-1}))\\ 0 & d^{k+1}\end{array}\right)\\ &= \left(\begin{array}{cc} 1 & c(1+d+d^2+\cdots + d^k)\\ 0 & d^{k+1}\end{array}\right). \end{align*}$ That is exactly the formula we have evaluated at $k+1$. Therefore, if the formula holds for $k$, then it holds for $k+1$ as well.

So: the formula holds for $n=1$; and if it holds for $n=k$, then it also holds for $n=k+1$. By Mathematical Induction, we conclude that the formula holds for all $n$.

  • 0
    Oh, I see. I had multiplied the matrices the wrong way. Many thanks!2011-06-09
4

Letting $a_n$ be the upper right hand corner of $A^n$, and assuming it is obvious that the lower right corner of $A^n$ is $d^n$, and the left column is $[1,0]^T$, we get:

$A^{n+1} = A^n A = \left[ {\begin{array}{cc} 1 & a_n \\ 0 & d^n \\ \end{array} } \right] \left[ {\begin{array}{cc} 1 & c \\ 0 & d \\ \end{array} } \right]$

This gives us $a_{n+1} = c + d a_n$, with $a_1=c$.

In particular, then $a_n = c + cd + cd^2 + ... + cd^{n-1} = c\frac{d^n-1}{d-1}$.

So:

$A^n = \left[ {\begin{array}{cc} 1 & c\frac{d^n-1}{d-1} \\ 0 & d^n \\ \end{array} } \right]$

  • 0
    Just wanted to point out that Thomas Andrews' answer in terms of ${d^n-1}\over{d-1}$ works for $n \leq 0$. And in the limit $d \to 1$ the fraction reduces to $n$, which again yields the correct result.2011-07-24
3

For this particular matrix, it is easy enough to compute the first few powers and conjecture a guess to prove by induction, but there are a lot of matrices (even $2\times 2$ matrices) where trying to find a pattern is significantly harder. The following method works more generally:

  1. Diagonalize $A$, that is, write $A=SDS^{-1}$ where $S$ is invertible and $D$ is diagonal. In general, you may have to use Jordan normal form, which will make things complicated but still solvable.

  2. $A^n=(SDS^{-1})^n= SD^nS^{-1}$. This is easy to compute because if $D=\operatorname{diag}(d_1,d_2,\ldots, d_k)$, then $D^n=\operatorname{diag}(d^n_1,d^n_2,\ldots, d^n_k)$.

In our particular case, if $d\neq 1$, the matrix is diagonalizable, and we have $D=\pmatrix{1 & 0 \\ 0 & d}$, $S=\pmatrix{1 & \frac{c}{d-1} \\ 0 & 1}$, and so $A^n=\pmatrix{1 & \frac{c}{d-1} \\ 0 & 1}\pmatrix{1 & 0 \\ 0 & d^n}\pmatrix{1 & \frac{-c}{d-1} \\ 0 & 1}$

1

A matrix can be looked at as machine that does something to the plane $\mathbb R^2$, in this case it takes a point $(x,y)$ and transports it to a point (x',y') along the direction $(c, d-1)$ by a factor of $y$ (it transports a point along the line with slope $\frac{d-1}{c}$, so repeated applications shouldn't take it off this line). Notice, the factor has nothing to do with $x$, so we have to just see how the new $y$'s are being formed. So, repeated application of $A$ means $(x,y) \mapsto (x,y)+y(c,d-1) \mapsto ((x,y)+ y(c,d-1)) + dy(c,d-1) \mapsto \ldots$. That is, $(x,y) \mapsto (x,y)+(1+d+d^2+\ldots)y(c,d-1)$. That is: $(x,y) \mapsto (x,y) + y(c\sum d^k,d^{n}-1)$. Which you can write back in matrix form.