# Is this proof by induction set out well?

• Jun 20th 2011, 05:05 AM
alexgeek
Is this proof by induction set out well?
Just wanted to check that this proof is set out correctly and that the last statement is logically correct:

Question

Quote:

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

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$
• Jun 20th 2011, 05:16 AM
Prove It
Re: Is this proof by induction set out well?
Quote:

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

Question

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$.
• Jun 20th 2011, 05:23 AM
alexgeek
Re: Is this proof by induction set out well?
That seems more clear thanks. Would you advise against writing is symbolically?

btw, I think you have to change the tags in your sig.
• Jun 20th 2011, 06:19 AM
Re: Is this proof by induction set out well?
Quote:

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

Question

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.
• Jun 20th 2011, 12:08 PM
emakarov
Re: Is this proof by induction set out well?
Quote:

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).
• Jun 20th 2011, 01:36 PM
alexgeek
Re: Is this proof by induction set out well?
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
• Jun 20th 2011, 03:02 PM
Also sprach Zarathustra
Re: Is this proof by induction set out well?
Quote:

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

Question

$4^{2n}-1=16^n-1$
$16\equiv 1(\mod15)$
Hence, $16^n\equiv 1^n(\mod15)$.
$16^n\equiv 1=(\mod15)$ or $4^{2n}\equiv 1(\mod15)$