# Mathematical Induction Matrix Example

I'm a little rusty and I've never done a mathematical induction problem with matrices so I'm needing a little help in setting this problem up.

Show that $$\begin{bmatrix}1&1\\1&1\end{bmatrix}^{n} = \begin{bmatrix}2^{(n-1)}&2^{(n-1)}\\2^{(n-1)}&2^{(n-1)}\end{bmatrix}$$ for every $n\ge 1$.

-
yes, just realized I left something off – cele Jun 25 '14 at 15:25
First show that it's true for $n=1$ (obvious). Then assume that it's true for $n$, and compute the value at $n+1$ by multiplying out the matrices. – katrielalex Jun 25 '14 at 15:28
@gnometorule, after looking at this problem with a professor I know, they suggested induction. As I've mentioned, I'm a little rusty, just getting back into higher math so I went with their suggestion – cele Jun 25 '14 at 15:28
nice little problem! 1up – John Smith Jun 25 '14 at 15:30
My comment was written when you were still missing the n-exponent. – gnometorule Jun 25 '14 at 15:36

The case $n=1$ is clear since $2^0 = 1$. So suppose that $$\begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix}^n = \begin{pmatrix} 2^{n-1}&2^{n-1} \\ 2^{n-1} & 2^{n-1}\end{pmatrix} \quad \quad *$$ for some $n \geq 1$ and let us prove that $$\begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix}^{n+1} = \begin{pmatrix} 2^{n}&2^{n} \\ 2^{n} & 2^{n}\end{pmatrix}.$$ We have $$\begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix}^{n+1} = \begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix}^{n} \begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix} \overset{*}{=} \begin{pmatrix} 2^{n-1}&2^{n-1} \\ 2^{n-1} & 2^{n-1}\end{pmatrix}\begin{pmatrix} 1&1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} 2\cdot 2^{n-1}&2\cdot 2^{n-1} \\ 2\cdot 2^{n-1} & 2\cdot 2^{n-1}\end{pmatrix} =\begin{pmatrix} 2^{n}&2^{n} \\ 2^{n} & 2^{n}\end{pmatrix}.$$
And thus the relation is true for every $n \in \mathbb{N}$
It is clearly true for $n=1$. Assume it's true for $n$. Then $$\begin{pmatrix}1&1\\1&1\end{pmatrix}^{n+1}=\begin{pmatrix}1&1\\1&1\end{pmatrix}\begin{pmatrix}2^{(n-1)}&2^{(n-1)}\\2^{(n-1)}&2^{(n-1)}\end{pmatrix}=\begin{pmatrix}2^{(n-1)}+2^{(n-1)}&2^{(n-1)}+2^{(n-1)}\\2^{(n-1)}+2^{(n-1)}&2^{(n-1)}+2^{(n-1)}\end{pmatrix}=\begin{pmatrix}2^n&2^n\\2^n&2^n\end{pmatrix}$$
So it's true for $n+1$. By induction it is true for all $n$.