How can I show that $\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^n = \begin{pmatrix} 1 & n \\ 0 & 1\end{pmatrix}$?

Solution 1:

The matrix $$N=\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$ is nilpotent with index 2 of nilpotency: $N^2=0$ so by the binomial formula we have

$$\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}^n=(I_2+N)^n=\sum_{k=0}^n {n\choose k}N^k={n\choose 0}I_2+{n\choose 1}N=I_2+nN=\begin{pmatrix} 1& n\\ 0 & 1 \end{pmatrix}$$

Solution 2:

Use induction on $n$.

(1) Prove the base case (trivial), perhaps even establish the case for $n = 2$ (two base cases here are not necessary, but as you found, it helps reveal the pattern.)

(2) Then assume it holds for $n = k$.

(3) Finally, show that from this assumption, it holds for $n = k+1$.

You've established the base case(s). Now, (2) assume the inductive hypothesis (IH) $$\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} \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^k \quad \overset{IH}{=} \quad \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix} \begin{pmatrix} 1 & k \\ 0 & 1\end{pmatrix}=\quad\cdots$$

I think you can take it from here!

Solution 3:

Powers of matrices occur in solving recurrence relations.

If you write $$ \begin{pmatrix} x_{n+1} \\ y_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix} \begin{pmatrix} x_n \\ y_n \end{pmatrix} $$ then clearly $$ \begin{pmatrix} x_{n} \\ y_{n} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}^n \begin{pmatrix} x_0 \\ y_0 \end{pmatrix} $$ and also $$ x_{n+1}=x_n+y_n, \qquad y_{n+1}=y_n $$ from which you get $$ x_n = x_0 + n\ y_0, \qquad y_n = y_0 $$ The first column of $A^n$ is given by taking $x_0=1$ and $y_0=0$, and so is $(1 \ 0)^T$.

The second column is given by taking $x_0=0$ and $y_0=1$, and so is $(n \ 1)^T$.