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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(k)} )

Example

Theorem. Every integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n > 1} can be written as a product of primes.

Proof. Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n)} represent "The integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} can be written as a product of primes.

Basis Step. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(2)} : 2 is prime — verified.

Inductive step. For some $k>1$, assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(2)} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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\geq k+1-3\geq 8$. By the inductive hypothesis: $k+1-3=a3+b5$, where $a,b\in \mathbb {Z} ^{+}$.

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

So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(k+1)} is true. This proves the inductive step. The general result follows by the principle of strong mathematical induction.