MATH 302 Lecture 12

« previous | Monday, October 10, 2011 | next »

Strong Induction

Same as mathematical induction, only assume that all previous steps are true(not just an arbitrary $P(k)$)

Example

Theorem. Every integer $n>1$ can be written as a product of primes.

Proof. Let $P(n)$ represent "The integer $n$ can be written as a product of primes.

Basis Step. $P(2)$: 2 is prime — verified.

Inductive step. For some $k>1$, assume $P(2)$, $P(3)$, …, $P(k)$ are true. Consider $k+1$: There are two cases:

1. $k+1$ is prime — done
2. $k+1=a\cdot b$, where $1<a,b<k+1$

For the second case, by the inductive hypothesis, let

$a=p_1{p}_2\cdots p_l$

and

$b=q_1{q}_2\cdots q_m$

. for primes

$p_1$

,

$q_1$

,

$p_2$

,

$q_2$

, …. Then

$k+1=a\cdot b=p_1{p}_2\cdots p_n\cdot q_1{q}_2\cdots q_n$

is also a product of primes. Therefor

$P(k+1)$

is a product of primes and thus

$P(n)$

is true by the principle of mathematical induction.

Q.E.D.

Another Example

What numbers can be represented as a sum of non-negative multiples of 3 and 5?

Conjecture P(n): Any number ≥ 8 can be written as such a sum.

Basis step.

1. P(8): 8 = 1(3) + 1(5)
2. P(9): 9 = 3(3) + 0(5)
3. P(10): 10 = 0(3) + 2(5)

Inductive step. Assume that P(8), ..., P(k) are true where k ≥ 10. Consider n = k + 1 where k + 1 ≥ 11 and $k\ge k+1-3\ge 8$. By the inductive hypothesis: $k+1-3=a3+b5$, where $a,b\in {\mathbb{\mathbb{Z}}}^{+}$.

$k+1=(a+1)3+b5$

So $P(k+1)$ is true. This proves the inductive step. The general result follows by the principle of strong mathematical induction.