induction «

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

Tag Archive

Matrices + Proof by Induction = magic

Links