Proof by Mathematical Induction?

Question

Okay, I always get stuck proving things. I proved that it is true from the first value. I know that now I have to prove that it is true for $n+1$ to show that its true for any $n$. Below I wrote what I'm trying to prove.

$$ A^{n} = \begin{bmatrix} \cos n\theta & -\sin n\theta \\ \sin n\theta & \cos n\theta \end{bmatrix}, \quad n \ge 1. $$

Okay so now I'm looking at

$$ A^{n+1} $$

and I broke this into

$$ A^{n+1} = A^{n}A $$

and now I'm stuck.... I know what A is. I just don't know what to do with the $$ A^{n} $$

Also, just a quick side question. This is the first time I tried to format it. However, I couldn't figure out the code for greater than equal to. Does anyone know what that is? Thanks.

Answer 1

I am going to assume you understand the premise of induction.

Knowing this, you should realize that the power of induction comes from the ability to represent an iteration of the result you are trying to prove in terms of a previous iteration. This means you must find a way of tying in your result somewhere.

There are two options. One is to start with $A^{n+1}$ and look for $$ A^{n} = \begin{bmatrix} \cos n\theta & -\sin n\theta \\ \sin n\theta & \cos n\theta \end{bmatrix} $$

somewhere in $ A^{n+1} $. However, we don't know what $A^{n+1}$ is yet. Our next option is to take $A^n$ and multiply by $A$ and look for $$ \begin{bmatrix} \cos{((n+1)\theta)} & -\sin{((n+1)\theta)} \\ \sin{((n+1)\theta)} & \cos{((n+1)\theta)} \end{bmatrix}. $$

So the next step is to do $A^nA$ as you indicated. You should already be thinking about trigonometric identities, because you have to multiple trig functions and simplify them to terms of only a single $\cos$ or $\sin$.

The two trig functions that will likely come into play here are $\cos(a + b) = \cos(a)\cos(b) - \sin(a)\sin(b)$ and $\sin(a + b) = \sin(a)\cos(b) + \cos(a)\sin(b)$. Do you see why these might be useful?

Answer 2

Ok so in your induction step you assume that the statement holds true for some $n$ greater than or equal to your base case. You then want to prove that it holds for $n+1$. As you noted $A^{n+1}=A^nA$. But since we are now assuming that the statement holds for $n$, we have

$A^n=\begin{bmatrix} \cos n\theta & -\sin n\theta \\ \sin n\theta & \cos n\theta \end{bmatrix} $

So multiply the two matrices and use some trig identities to get what $A^{n+1}$ of the proper form.

Answer 3

Given $\mathbf A=\begin{bmatrix}\cos \theta&-\sin \theta\\ \sin \theta & \cos \theta\end{bmatrix}$ prove $\forall n\geqslant 1, \mathbf A^n = \begin{bmatrix}\cos n\theta&-\sin n\theta\\ \sin n\theta & \cos n\theta\end{bmatrix}$

That's our predicate: $\mathbb P(n) \equiv \mathbf A^n = \begin{bmatrix}\cos n\theta&-\sin n\theta\\ \sin n\theta & \cos n\theta\end{bmatrix}$

Induction is: $\forall n\in \mathbb Z^+ : [\mathbb P(1) \land (\mathbb P(n)\to \mathbb P(n+1))] \vdash \forall n\in \mathbb Z^+ : [\mathbb P(n)]$

---

Trivially $\mathbf A^1 = \begin{bmatrix}\cos 1\theta&-\sin 1\theta\\ \sin 1\theta & \cos 1\theta\end{bmatrix}$. So the base case is true.

$$\mathbb P(1)$$

Now we assume $\mathbf A^n = \begin{bmatrix}\cos n\theta&-\sin n\theta\\ \sin n\theta & \cos n\theta\end{bmatrix}$

Then it would follow that: $\mathbf A^{n+1} = \begin{bmatrix}\cos n\theta & -\sin n\theta\\ \sin n\theta & \cos n\theta\end{bmatrix}\begin{bmatrix}\cos \theta&-\sin \theta\\ \sin \theta & \cos \theta\end{bmatrix} \\ \ddots \qquad\text{(use matrix multiplication and trig identities)}\\ \mathop{=}^? \begin{bmatrix}\cos ((n+1)\theta)&-\sin ((n+1)\theta)\\ \sin ((n+1)\theta) & \cos ((n+1)\theta)\end{bmatrix}\qquad\text{(does it?)}$

If it does then $$\forall n\in \mathbb Z^+:\mathbb P(n)\to \mathbb P(n+1)$$