# Thread: Is this proof by induction set out well?

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

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

2. ## Re: Is this proof by induction set out well?

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 \displaystyle n = 1$

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

which is divisible by $\displaystyle \displaystyle 15$.

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

Let $\displaystyle \displaystyle n = k + 1$

\displaystyle \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 \displaystyle 15$.

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

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

4. ## Re: Is this proof by induction set out well?

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

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

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

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

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

5. ## Re: Is this proof by induction set out well?

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

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

7. ## Re: Is this proof by induction set out well?

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

Question

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