# Matrices + Proof by Induction = magic

Just though I’d share a proof which made my happy, and shows how elegant proof by induction can be.

$\textrm{Let } P(n) \textrm{ be the statement that} M^n = \begin{pmatrix} 1-3n&9n\\-n&1+3n \end{pmatrix} \\ \textrm{where } M = \begin{pmatrix}-2&9\\-1&4\end{pmatrix}$

Prove $P(k)$ is true $\forall k \in \mathbb{N}$

$\textrm{Let } k = 1$
$\Rightarrow M^1 = \begin{pmatrix}1 - 3&9\times 1\\-1&1+3\end{pmatrix} = \begin{pmatrix}-2&9\\-1&4\end{pmatrix}\\ \Rightarrow P(1) \textrm{ is clearly true.}$

$\textrm{Now suppose that } P(k) \textrm{ is true for some } k \in \mathbb{N}$
$\Rightarrow M^k = \begin{pmatrix} 1-3k&9k\\-k&1+3k \end{pmatrix}$
$\textrm{Then}$
$M^{k+1} = MM^k = \begin{pmatrix}-2&9\\-1&4\end{pmatrix}\begin{pmatrix} 1-3k&9k\\-k&1+3k \end{pmatrix}$
$= \begin{pmatrix}-2 + 6k - 9k&-18k+9+27k\\-1+3k-4k&-9k+4+12k\end{pmatrix}\\ \\ =\begin{pmatrix}-2-3k&9k+9\\-1-k&4+3k\end{pmatrix} \\ \\ = \begin{pmatrix}1-3(k+1)&9(k+1)\\-(k+1)&1+3(k+1)\end{pmatrix} \Rightarrow P(k+1) \textrm{ is true }$

Since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ the result follows by mathematical induction

## 5 thoughts on “Matrices + Proof by Induction = magic”

1. Ozlem Dirgin says:

You can’t imagine how it’s useful for me!
I’m writing a mathematic portfolio for IBO and I have to prove some terms of matrices in induction. I was searching for it and I found it!
You’re really wonderful!
Thanks for it :)

Ozlem, from Turkey..

1. jebavarde says:

:D

2. Joel says:

I am doing a Mathematical Investigation, also for the IB. I wish this was useful, but it isnt quite! haha so frustrating.

2. If you want to read a reader’s feedback :) , I rate this post for four from five. Detailed info, but I have to go to that damn msn to find the missed parts. Thanks, anyway!

3. I’m currently working on a homework problem very similar to this (

prove A^n = [ f_n+1, f_n ]
[ f_n, f_n-1]

where f_n is the nth fibonacci number. I wasn’t sure if I was going about it the right way, but after seeing your proof I’m a lot more confident. Thanks =)