Matrix $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ to a large power

This question already has an answer here:

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

    8 answers

Solutions Collecting From Web of "Matrix $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$ to a large power"

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}

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}
$$

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) $.

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.