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

Matrices + Proof by Induction = magic

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

  2. 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 =)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s