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:

$k+1$ is prime — done
$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.

P(8): 8 = 1(3) + 1(5)
P(9): 9 = 3(3) + 0(5)
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\geq k+1-3\geq 8$ . By the inductive hypothesis: $k+1-3=a3+b5$ , where $a,b\in \mathbb {Z} ^{+}$ .