# Solve this

Question:

Let $A=\left[\begin{array}{lll}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$.

Solution:

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

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

$A^{1}=\left[\begin{array}{ccc}1 & 1 & 1(1+1) / 2 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{array}\right]=\left[\begin{array}{lll}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(m+1) / 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,

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

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

By definition of integral power of matrix, we have

$A^{m+1}=A^{m} A$

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

$\Rightarrow A^{m+1}=\left[\begin{array}{ccc}1+0+0 & 1+m+0 & 1+m+m(m+1) / 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+2 m+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}+3 m+2\right) / 2 \\ 0 & 1 & 1+m \\ 0 & 0 & 1\end{array}\right]$

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

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

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

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