Is this proof by induction set out well?

**alexgeek** · June 20th 2011, 05:05 AM

Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

Question

Use mathematical induction to prove that $4^{2n}-1$ is divisible by 15 for all positive integers n.

Answer

Let $P$ be $4^{2n}-1$ is divisible by 15.
Assuming $u_n = 4^{2n}-1$ to be true [1] ( $u_n = 15k$ ),
$u_{n+1} = 4^{2(n+1)} -1 = 4^{2n+2} - 1$
$u_{n+1} = 16 \times 4^{2n} - 1$
From [1], $u_{n+1} = 16(u_n + 1) -1$
$u_{n+1} = 16(15k + 1) -1$
$u_{n+1} = 16(15k)+ 16 -1 = 16(15k) - 15 = 15(16k-1)$
Therefore if $u_n$ is divisible by 15, then so is $u_{n+1}$ ,
When $n =1$ , $u_n = 4^{2 \times 1} -1 = 15$ . Therefore the basis case holds true.
Therefore by mathematical induction,
$\forall n \in \mathbb{Z} , u_n \implies u_{n+1}, u_n \therefore P$

**Prove It** · June 20th 2011, 05:16 AM

Originally Posted by alexgeek

Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

Question

Answer

Base step: $\displaystyle n = 1$

$\displaystyle \begin{align*} 4^{2n} - 1 &= 4^{2\cdot 1} - 1 \\ &= 4^2 - 1 \\ &= 16 - 1 \\ &= 15 \end{align*}$

which is divisible by $\displaystyle 15$ .

Inductive step: Assume $\displaystyle 4^{2k} - 1 = 15m$ (i.e. it's divisible by $\displaystyle 15$ )

Let $\displaystyle n = k + 1$

$\displaystyle \begin{align*} 4^{2n} - 1 &= 4^{2(k + 1)} - 1\\ &= 4^{2k + 2} - 1 \\ &= 4^{2k}4^2 - 1 \\ &= (15m + 1)4^2 - 1 \\ &= 4^2\cdot 15m + 4^2 - 1 \\ &= 4^2\cdot 15m + 16 - 1\\ &= 4^2\cdot 15m + 15 \\ &= 15(4^2 \cdot m + 1) \end{align*}$

which is divisible by $\displaystyle 15$ .

Therefore $\displaystyle 4^{2n} - 1$ is divisible by $\displaystyle 15$ for all positive integer $\displaystyle n$ .

**alexgeek** · June 20th 2011, 05:23 AM

That seems more clear thanks. Would you advise against writing is symbolically?

btw, I think you have to change the tags in your sig.

**Archie Meade** · June 20th 2011, 06:19 AM

Originally Posted by alexgeek

Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

Question

Answer

You could shorten your proof considerably by writing

$u_n=4^{2n}-1$

$u_{n+1}=4^{2(n+1)}-1=4^{2n+2}-1=(16)4^{2n}-1=(15)4^{2n}+4^{2n}-1$

$\Rightarrow\ u_{n+1}=(15)4^{2n}+u_n$

so that if $u_n$ is a multiple of 15, then $u_{n+1}$ will also be a multiple of 15.

**emakarov** · June 20th 2011, 12:08 PM

Originally Posted by alexgeek

Would you advise against writing is symbolically?

Good question. See an example of a proof on p. 9 of "Mathematical Writing" by Knuth, Larrabee, and Roberts (PDF).

**alexgeek** · June 20th 2011, 01:36 PM

I was like ooh that looks interesting then saw that it's 112 pages long. I'll keep it until next week when my exams are over.
Thank you though.

Edit. Oh you said page 9. Brain is melting from too much maths sorry