Question
If \[ A = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} \] prove that \[ A^n = \begin{bmatrix} 1 & n & \frac{n(n+1)}{2} \\ 0 & 1 & n \\ 0 & 0 & 1 \end{bmatrix} \] for all \(n \in \mathbb{N}\).
Solution (Mathematical Induction)
Step 1: Base Case (n = 1)
\[ A^1 = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} \] RHS for \(n=1\): \[ \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} \] ✔ TrueStep 2: Assume for \(n = k\)
\[ A^k = \begin{bmatrix} 1 & k & \frac{k(k+1)}{2} \\ 0 & 1 & k \\ 0 & 0 & 1 \end{bmatrix} \]Step 3: Prove for \(n = k+1\)
\[ A^{k+1} = A^k \cdot A \] \[ = \begin{bmatrix} 1 & k & \frac{k(k+1)}{2} \\ 0 & 1 & k \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} \]Step 4: Multiply
\[ = \begin{bmatrix} 1 & k+1 & \frac{k(k+1)}{2} + k + 1 \\ 0 & 1 & k+1 \\ 0 & 0 & 1 \end{bmatrix} \]Step 5: Simplify
\[ \frac{k(k+1)}{2} + k + 1 = \frac{(k+1)(k+2)}{2} \]Step 6: Final Form
\[ A^{k+1} = \begin{bmatrix} 1 & k+1 & \frac{(k+1)(k+2)}{2} \\ 0 & 1 & k+1 \\ 0 & 0 & 1 \end{bmatrix} \] ✔ True for \(k+1\)Final Result
\[
A^n =
\begin{bmatrix}
1 & n & \frac{n(n+1)}{2} \\
0 & 1 & n \\
0 & 0 & 1
\end{bmatrix}
\]
Hence proved.