Question

Let $A=\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 1\\ 0& 0& 1\end{array}\right]$. Use the principle of mathematical induction to show that

$A^n=\left[\begin{array}{ccc}1& n& n(n+1)/2\\ 0& 1& n\\ 0& 0& 1\end{array}\right]$ for every positive integer n.

Answer 1

We shall prove the result by the principle of mathematical induction on n.

Step 1: If n = 1, by definition of integral power of a matrix, we have

$A^1=\left[\begin{array}{ccc}1& 1& 1\left(1+1\right)/2\\ 0& 1& 1\\ 0& 0& 1\end{array}\right]=\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 1\\ 0& 0& 1\end{array}\right]=A$

Thus, the result is true for n = 1.

Step 2: Let the result be true for n = m. Then,

$A^m=\left[\begin{array}{ccc}1& m& m\left(m+1\right)/2\\ 0& 1& m\\ 0& 0& 1\end{array}\right]$ ...(1)

Now, we shall show that the result is true for $n=m+1$.
Here,

$$\begin{gathered} A^{m+1}=\left[\begin{array}{ccc}1& m+1& m+1\left(m+1+1\right)/2\\ 0& 1& m+1\\ 0& 0& 1\end{array}\right] \\ \Rightarrow A^{m+1}=\left[\begin{array}{ccc}1& m+1& \left(m+1\right)\left(m+2\right)/2\\ 0& 1& m+1\\ 0& 0& 1\end{array}\right] \end{gathered}$$

By definition of integral power of matrix, we have
$$\begin{gathered} A^{m+1}=A^{m}A \\ \Rightarrow A^{m+1}=\left[\begin{array}{ccc}1& m& m\left(m+1\right)/2\\ 0& 1& m\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 1\\ 0& 0& 1\end{array}\right]\left[\mathrm{From}\mathrm{eq}.\left(1\right)\right] \\ \Rightarrow A^{m+1}=\left[\begin{array}{ccc}1+0+0& 1+m+0& 1+m+m\left(m+1\right)/2\\ 0+0+0& 0+1+0& 0+1+m\\ 0+0+0& 0+0+0& 0+0+1\end{array}\right] \\ \Rightarrow A^{m+1}=\left[\begin{array}{ccc}1& 1+m& \left(2+2m+m^2+m\right)/2\\ 0& 1& 1+m\\ 0& 0& 1\end{array}\right] \\ \Rightarrow A^{m+1}=\left[\begin{array}{ccc}1& 1+m& \left(m^2+3m+2\right)/2\\ 0& 1& 1+m\\ 0& 0& 1\end{array}\right] \\ \Rightarrow A^{m+1}=\left[\begin{array}{ccc}1& 1+m& \left(m+1\right)\left(m+2\right)/2\\ 0& 1& 1+m\\ 0& 0& 1\end{array}\right] \end{gathered}$$


This shows that when the result is true for n = m, it is also true for n = m + 1.

Hence, by the principle of mathematical induction, the result is valid for any positive integer n.