Strong Induction
For a normal case of mathematical induction you can prove that a statement holds for all numbers from a particular start point.
It uses a base case so show that it holds for an individual number and an induction rule that proves that it holds for all numbers following.
- Prove that the property holds for the natural number $n=0$
- Prove that if the property holds for $n=0,1,\ldots,m$ (and not just for m) then it holds for $n=m+1$.
Can also be used to prove a property for all integers greater than or equal to some particular natural number $b$.
Example 1
Every natural number $n \geq 2$, is a prime or product of primes.
Base Case
Take $n=2$
Then $n$ is a prime number.
Inductive Step
Assume that the property holds for $n=m$ so every number $i$ such that $2\leq i\leq m$ is a prime or a product of primes.
Now consider $n=m+1$.
We proceed by considering cases.
Case 1
$m+1$ is prime.
There is nothing to prove.
Case 2
$m+1$ is not prime.
So $m+1=k\times l$, where $k\neq1,\ k\neq m+1$ and $l\neq 1,\ l\neq\ m+1$
So $k\geq2,\ l\geq2,\ k\leq m,\ l \leq m$
So $k=P_1\ldots P_n,\ l=Q_1\ldots Q_m$. Then $k\times l$ is a product of primes.
Example 2
For any integer $n\geq1$, if $x_1,x_2,\ldots,x_n$ are $n$ numbers, then no matter how the parentheses are inserted into their product, the number of multiplications used to compute the products is $n-1$.
As the number are all individual you can’t use tricks like using already computed values to speed up the computation.
Base Case
\(X_1 \text{ for } n=1,\ n-1=0\)
Induction Step
Suppose that no matter how I put parentheses on a sequence of $i$ elements, where $1\leq i\leq m$, I need $m-1$ multiplications.
Consider, where $1\leq l \leq m$:
\[\underbrace{\underbrace{(x_1\times\ldots)}_{l}\times\underbrace{(\ldots\times x_{m+1})}_{m+1-l}}_{m+1}\]By induction hypothesis:
\[\require{cancel}\cancel{l}-1+m+1-\cancel{l}-\cancel{1}+\cancel{1}=(m+1)-1\]This proves that the property holds for the next value to infinitude. $\square$