Matrix $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ to a large power Compute
$\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}^{99}$
What is the easier way to do this other than multiplying the entire thing out?
Thanks
 A: Following the comment of Matt Samuel:
$$
\begin{pmatrix}
1 & 1 \\
0 & 1 
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
0 & 1 
\end{pmatrix} = 
\begin{pmatrix}
1 & 2 \\
0 & 1 
\end{pmatrix}
$$
$$
\begin{pmatrix}
1 & 1 \\
0 & 1 
\end{pmatrix}^3
= 
\begin{pmatrix}
1 & 3 \\
0 & 1 
\end{pmatrix}
$$
$$
\begin{pmatrix}
1 & 1 \\
0 & 1 
\end{pmatrix}
\begin{pmatrix}
1 & n \\
0 & 1 
\end{pmatrix}
=
\begin{pmatrix}
1 & n+1 \\
0 & 1 
\end{pmatrix}
$$
A: Consider the case of a general $2 \times 2$ matrix times $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$:
$\left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \times \left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right) = \left( \begin{matrix} a & a + b \\ c & c + d \end{matrix} \right) $.
Thus, we see that multiplying any $2 \times 2$ matrix by $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$ once leaves the entries in the first column unchanged and increments the entries in the second column by the corresponding entries from the first column.  Since our lower-left entry was zero and the upper-left entry was one, this has the effect of simply incrementing the upper-right entry by one but leaving the rest unchanged.
Therefore, since we begin with $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$ and multiply it by $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)$ 98 times, we see that $\left( \begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix} \right)^{99} = \left( \begin{matrix} 1 & 99 \\ 0 & 1 \end{matrix} \right) $.
A: There is a well-known general technique to raise something to a natural-number power. We first translate from base $10$ to base $2$:
$$99_{10} = 1100011_2$$
You can calculate the matrix to a power of two with a tower of squaring.
\begin{align}
\left(m^{2}\right)^2 &= m^{4} \\
\left(m^{4}\right)^2 &= m^{8} \\
\left(m^{8}\right)^2 &= m^{16} \\
\end{align}
So with $8$ squarings you can calculate all the factors needed.  Then multiply the ones corresponding to a $1$ bit in the binary representation of $99$, and you have your answer. So $8 + 3$ multiplications would be required.
This method does not depend on the value of the matrix.
A: Hint One option that avoids explicit use of induction is to write the matrix as
$$I + J,$$
where $$J := \pmatrix{0 & 1\\0 & 0}.$$
Since $J^2 = 0$, each term in the expansion of
$$(I + J)^{99}$$
with two or more factors of $J$ is zero.
Edit As Will points out, since $I$ and $J$ commute, we can expand the power as
\begin{align}\require{cancel}
(I + J)^{99}
&= \sum_{a = 0}^{99} {99 \choose a} I^{99 - a} J^a \\
&= I + 99 J + \sum_{a = 2}^{99} {99 \choose a} J^a \\
&= I + 99 J + \cancelto{0}{J^2 \sum_{a = 2}^{99} {99 \choose a}J^{a - 2}} \\
&= I + 99 J .
\end{align}
