Finding $A^n$ for a matrix 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.
 A: 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]$$
A: 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:


*

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

*$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}$$
A: 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$.
A: 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. 
