# If $$A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ \end{bmatrix}$$, prove that $A^n = \begin{bmatrix} 3^{n-1} & 3^{n-1} & 3^{n-1} \\ 3^{n-1} & 3^{n-1} & 3^{n-1} \\ 3^{n-1} & 3^{n-1} & 3^{n-1} \\ \end{bmatrix}$, for $$n \in N.$$

Toolbox:
• We use the principle of mathematical induction, where we need to prove P(n) is true for n=1, n=k, n=k+1
• If A is an m-by-n matrix and B is an n-by-p matrix, then their matrix product AB is the m-by-p matrix whose entries are given by dot product of the corresponding row of A and the corresponding column of B: $\begin{bmatrix}AB\end{bmatrix}_{i,j} = A_{i,1}B_{1,j} + A_{i,2}B_{2,j} + A_{i,3}B_{3,j} ... A_{i,n}B_{n,j}$
Let P(n)=$A^n=\begin{bmatrix} 3^{n-1} & 3^{n-1} & 3^{n-1} \\ 3^{n-1} & 3^{n-1} & 3^{n-1} \\ 3^{n-1} & 3^{n-1} & 3^{n-1} \\ \end{bmatrix}$ where $A=\begin{bmatrix}1 & 1& 1\\1 & 1& 1\\1& 1& 1\end{bmatrix}$ for n=1.
LHS:-$A^n=A^1=\begin{bmatrix}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\end{bmatrix}$
RHS:-$A^n=\begin{bmatrix}3^0 &3^0 &3^0\\3^0 &3^0 &3^0\\3^0 &3^0 &3^0\end{bmatrix}$
$\qquad\qquad=\begin{bmatrix}1 & 1 & 1\\1 & 1 & 1\\1 & 1 & 1\end{bmatrix}$
Hence P(n) is true for n=1.
Let it be true for n=k.
$A^k=\begin{bmatrix}3^{k-1} &3^{k-1}&3^{k-1}\\3^{k-1} &3^{k-1}&3^{k-1}\\3^{k-1} &3^{k-1}&3^{k-1}\end{bmatrix}$
Multiply both sides by A
LHS:-$A^k.A=A^{k+1}$
RHS:-$\begin{bmatrix}3^{k-1} &3^{k-1}&3^{k-1}\\3^{k-1} &3^{k-1}&3^{k-1}\\3^{k-1} &3^{k-1}&3^{k-1}\end{bmatrix}$.A
$A^{k+1}=\begin{bmatrix}3^{k-1} &3^{k-1}&3^{k-1}\\3^{k-1} &3^{k-1}&3^{k-1}\\3^{k-1} &3^{k-1}&3^{k-1}\end{bmatrix}\begin{bmatrix}1 & 1& 1\\1 & 1& 1\\1& 1& 1\end{bmatrix}$
$\quad\;\;=\begin{bmatrix}3^{k-1}+3^{k-1}+3^{k-1}&3^{k-1}+3^{k-1}+3^{k-1}&3^{k-1}+3^{k-1}+3^{k-1}\\3^{k-1}+3^{k-1}+3^{k-1}&3^{k-1}+3^{k-1}+3^{k-1}&3^{k-1}+3^{k-1}+3^{k-1}\\3^{k-1}+3^{k-1}+3^{k-1}&3^{k-1}+3^{k-1}+3^{k-1}&3^{k-1}+3^{k-1}+3^{k-1}\end{bmatrix}$
$\quad\;\;=\begin{bmatrix}3.3^{k-1}&3.3^{k-1}&3.3^{k-1}\\3.3^{k-1}&3.3^{k-1}&3.3^{k-1}\\3.3^{k-1}&3.3^{k-1}&3.3^{k-1}\end{bmatrix}$
$\quad\;\;=\begin{bmatrix}3^k & 3^k & 3^k\\3^k & 3^k & 3^k\\3^k & 3^k & 3^k\end{bmatrix}$
$\quad\;\;=\begin{bmatrix}3^{(k+1)-1} & 3^{(k+1)-1} & 3^{(k+1)-1}\\3^{(k+1)-1} & 3^{(k+1)-1} & 3^{(k+1)-1}\\3^{(k+1)-1} & 3^{(k+1)-1} & 3^{(k+1)-1}\end{bmatrix}$
Hence P(n) is true for n=k+1.
By principle of mathematical induction P(n) is true for all $n\in N$.