# 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.