Is this proof by induction set out well?

Printable View

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

Answer

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$
June 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

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$ .
June 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.
June 20th 2011, 06:19 AM
Archie Meade

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

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

Answer

Or,

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