# Linear algebra identity proof by induction

I want to prove that $\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^n=\begin{pmatrix}1 & n\\ 0 & 1\end{pmatrix}, n=1,2,3\dots$ by induction, I've come this far:

Basis:

$U_1:\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^1=\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$.

Inductive step: We then assume that $U_k$ is true

$U_k:\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^k=\begin{pmatrix}1 & k\\ 0 & 1\end{pmatrix}$

Then

$\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^{k+1}=\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^k+\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$

I'm not sure if the last part is right and how to proceed...

-
The $+$ should be a $\cdot$ in the last line. – Julian Kuelshammer Feb 8 '13 at 10:00
@JulianKuelshammer But whats the (induction-wise) argument for multiplying the matrix on the left side of U_k? – user37158 Feb 8 '13 at 11:12
matrix multiplication is associative? – Julian Kuelshammer Feb 8 '13 at 11:27

$$\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^{k+1}=\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^k+\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$$ This will be $$\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^{k+1}=\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}^k.\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$$ $$=\begin{pmatrix}1 & k\\ 0 & 1\end{pmatrix}.\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix}$$ $$=\begin{pmatrix}1 & k+1\\ 0 & 1\end{pmatrix}.$$
So should it be a + or $\cdot$ in the last line as noted in the comments underneath the question? – dal102 Jun 30 '13 at 4:31
You first split the matrix into diagonal and non-diagonal parts: $$\begin{pmatrix}1 & 1\\ 0 & 1\end{pmatrix} = I_{2} + A = \begin{pmatrix}1 & 0\\ 0 & 1\end{pmatrix} + \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$$ Using the fact: $$A^2 = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}^2 = \begin{pmatrix}0 & 0\\ 0 & 0\end{pmatrix} = 0.$$ Binomial theorem immediately give you $(I_{2}+A)^n = I_{2} + n A + \binom{n}{2} A^2 + ... = I_{2} + n A$.
Similarly tricks can be applied to other $n \times n$ matrices. For example, the $3 \times 3$ matrix $$B = \begin{pmatrix}0 & 1 & 0\\ 0 & 0 & 1\\0 & 0 & 0\end{pmatrix}$$ satisfies $B^3 = 0$, this will lead to: \begin{align} \begin{pmatrix}\lambda& 1 & 0\\ 0 & \lambda & 1\\0 & 0 & \lambda\end{pmatrix}^n &= ( \lambda I_{3} + B )^n\\&= \lambda^n I_{3} + n \lambda^{n-1} B + \binom{n}{2} \lambda^{n-2} B^2 + \binom{n}{3}\lambda^{n-3} B^3 + ...\\ &= \begin{pmatrix}\lambda^n & n \lambda^{n-1} & \binom{n}{2}\lambda^{n-2}\\ 0 & \lambda^n & n \lambda^{n-1}\\0 & 0 & \lambda^n\end{pmatrix} \end{align}