Induction

Induction is basically another proof technique.
- … one that's particularly useful in discrete math.
- Induction is used to prove facts on integers \(\ge 1\).
- [We might start at 0 or some other value, but we'll stay with 1 for now.]
In a proof by induction, we'll establish two things about the fact we're trying to prove for \(n\ge 1\):
1. The fact is true for \(n=1\).
2. If the fact is true for \(n-1\), we can prove that it's true for \(n\).
If we can do that, have we proven that…
- it is true for \(n=1\)? Yes: showed it in (A).
- it is true for \(n=2\)? Yes: use (A) and (B).
- it is true for \(n=3\)? Yes: use (A) and (B) twice.
- it is true for \(n=4\)? Yes: use (A) and (B) three times.
- ⋮
We call (A) the base case and (B) the inductive case.
Or formally we have a proposition \(P(n)\) and we want to show that \(\forall n\in\mathbf{Z}(n\ge 1\rightarrow P(n))\).
- We do this by proving two things: \(P(1)\) and \(\forall n (P(n-1)\rightarrow P(n))\).
- We rely on this tautology: \[[P(1)\wedge \forall n (P(n-1)\rightarrow P(n))]\rightarrow \forall n(n\ge 1\rightarrow P(n))\]
A more formal version of the above: if we prove \(P(1)\) and \(\forall n (P(n-1)\rightarrow P(n))\), then we have:
- For \(n=2\), \[\begin{align*} P(1) \wedge \forall n (P(n-1)\rightarrow P(n)) &\rightarrow P(1) \wedge (P(1)\rightarrow P(2)) \\ &\rightarrow P(2)\,. \end{align*}\]
- Then for \(n=3\), \[\begin{align*} P(2) \wedge \forall n (P(n-1)\rightarrow P(n)) &\rightarrow P(2) \wedge (P(2)\rightarrow P(3)) \\ &\rightarrow P(3)\,. \end{align*}\]
- … and so on for every integer \(n\ge 1\).
An example proof by induction:
Example: For integers \(n\ge 1\), the sum \(1+2+\cdots+n = \sum_{i=1}^{n}i\) is \(\frac{n(n+1)}{2}\).

Proof: Base case: for \(n=1\), the summation is \(1\) and the formula gives \(\frac{1\cdot 2}{2}=1\).

Inductive case: Assume for induction that the conclusion is true for \(n-1\), that is \(1+2+\cdots+(n-1) = \frac{(n-1)n}{2}\). Then, consider the sum to \(n\): \[\begin{align*} 1+2+\cdots+(n-1)+n &= \frac{(n-1)n}{2} + n \\ &= \frac{(n-1)n+2n}{2} \\ &= \frac{n^2-n+2n}{2} \\ &= \frac{n(n+1)}{2}\,. \end{align*}\]

Thus we have the conclusion for \(n\). By induction, it is true for all integers \(n\ge 1\).∎
Note: the book phrases the proofs as \(P(k)\rightarrow P(k+1)\) for \(k\ge 1\) instead of \(P(n-1)\rightarrow P(n)\) for \(n\gt 1\).
- Obviously they are the same with \(k=n-1\).
- I find it's usually easier to get the details right when trying to conclude \(P(n)\).
- e.g. in the above proof, if proving for \(n+1\) we would have had to factor out and get \(\frac{(n+1)(n+2)}{2}\). Possible, but harder to notice.
- You can do whichever one you like. Some proofs will be easier with \(n\) and \(n+1\).
Example: \(n!\gt 2^n\) for integers \(n\ge 4\).

Proof: Base case: For \(n=4\), we have \(n!=24\gt 16=2^n\).

Inductive case: Assume for induction that \((n-1)!\gt 2^{n-1}\). Then, \[\begin{align*} n! &= n(n-1)! \\ &\gt n2^{n-1} \\ &\gt 2\cdot2^{n-1} \\ &= 2^{n} \,. \end{align*}\]

By induction, for integers \(n\ge 4\), we have \(n!\gt 2^n\).∎
Example: For all natural numbers, \(4\mid 5^n-1\).

Proof: Base case: For \(n=0\), we have \(4\mid 0\).

Inductive case: Assume for induction that \(4\mid 5^{n-1}-1\). Then, there is some \(k\) such that \(4k=5^{n-1}-1\) and \[\begin{align*} 5^{n}-1 &= 5\cdot 5^{n-1} - 1 \\ &= 5\cdot 5^{n-1} -5 +4 \\ &= 5(5^{n-1} -1) + 4 \\ &= 5(4k) + 4 \\ &= 4(5k+1)\,. \end{align*}\]

So we see that \(5^{n}-1\) is also divisible by 4 and by induction we have the conclusion for all natural numbers.∎
The recipe for an induction proof (or “weak induction” proof as we'll call it soon) is always the same:
- Prove the conclusion for the smallest \(n\) (call it \(a\)). Usually very easy.
- Use the conclusion for \(n-1\) to prove it for \(n\). (Or use \(n\) to prove for \(n+1\).)
- Conclude by induction that it's true for all integers \(n\ge a\).
One more way to think about induction: Let \(S\) be the set of values where the theorem is true.
- We show directly that \(a\in S\).
- We show that if \(n-1\in S\) then \(n\in S\).
- What values are in \(S\)?
Example: Define the sequence \(\{a_n\}\) as \(a_1=1\), and for \(n\ge 1\), \(a_{n+1} = \sqrt{1+2a_n}\).

Then all \(a_n\lt 4\).

Proof: Base case: For \(n=1\), we have \(1\lt 4\).

Inductive case: Assume for induction that \(a_n\lt 4\). Then, for \(a_{n+1}\) we have \[\begin{align*} a_{n+1} &= \sqrt{1+2a_n} \\ &\lt \sqrt{1+2\cdot 4} \\ &= \sqrt{9} \\ &= 3\,. \end{align*}\]

So, for all \(n\ge 1\), we have \(a_n\lt 4\).∎

Strong Induction

When we were looking at induction formally above, we showed that our predicate was true for \(P(1)\), then \(P(2)\), and then for \(n=3\) did this: \[P(2) \wedge (P(2)\rightarrow P(3)) \rightarrow P(3)\,.\]
- We didn't use the truth of \(P(1)\) in that step.
- … and we didn't need it in any proofs up to now.
There's no reason we can't use \(P(1)\wedge P(2)\wedge\cdots\wedge P(n-1)\) when proving \(P(n)\). They are all true by the same ideas.
- That is, instead of using this in our inductive step, \[P(n-1)\rightarrow P(n)\,,\] we can use \[(P(1)\wedge P(2)\wedge\cdots\wedge P(n-1))\rightarrow P(n)\,.\]
Doing inductive proofs this way is called strong induction.
- Using only \(P(n-1)\) as we have been doing is called weak induction.
Example: Every integer \(n\ge 2\) can be written as a product of prime numbers.

Proof: Base case: For \(n=2\), the value itself prime, so is the product of a single prime.

Inductive case: Assume for strong induction that for all \(2\le k\lt n\) that \(k\) can be written as the product of primes.

Case 1: \(n\) is prime. Then like the base case, it can be written as the product of a single prime.

Case 2: \(n\) is composite. Then by definition \(n\) has a factor \(2\le a\le n/2\), so that \(n=ab\). Then note that \( 2\le b = n/a \le n/2 \). Thus both \(a\) and \(b\) are less than \(n\). Then from the inductive hypothesis, both \(a\) and \(b\) can be written as the product of primes. Then \(n=ab\) can be written as the product of the prime factorizations of \(a\) and \(b\).∎
Example: Suppose it is decided that China will now only 4分 and 5分 coins no other currency. Prove that any amount over 12分 can be made using these coins.

Proof: Base case: We can form 12分 with three 4分 coins; 13分 with two 4分 and a 5分; 14分 with one 4分 and two 5分; and finally 15分 with three 5分 coins.

Inductive case: Assume for strong induction that for \(n\gt 15\), it is possible to make all amounts of \(k\)分 change, with \(12\le k\lt n\lt 15\). Then, consider making \(n\)分 in change. From the inductive assumption, it is possible to make \((n-4)\)分 in change. Add a 4分 to this to make \(n\)分.∎
Same theorem, but with weak induction:
Example: Suppose it is decided that China will now only 4分 and 5分 coins no other currency. Prove that any amount over 12分 can be made using these coins.

Proof: Base case: 12分 can be made using three 4分 coins.

Inductive case: For \(n\ge 12\), assume for induction that it is possible to make change for \(n\)分. Then, consider making \((n+1)\)分 in change.
Case 1: Making \(n\)分 in change requires at least one 4分 coin. If this is the case, take the change required to make \(n\)分 and replace a 4分 with a 5分. This gives \((n+1)\)分 in change.

Case 2: Making \(n\)分 in change requires no 4分 coins. Since we know that \(n\ge 12\), the change for \(n\)分 requires at least three 5分 coins. Take the change neede to make \(n\)分. Take away three 5分 coins and add four 4分 coins. That gives \((n+1)\)分 coins in change.∎
So, sometimes either weak or strong induction will do the job.
- Maybe it's harder to do with weak, or might be impossible.
- Like proof by contradiction, it never hurts to assume strong induction when you're sketching a proof.
- If you only needed \(n-1\), go back and pretend you were doing weak induction all along.