Proofs by induction
The (formally sloppy) principle of induction is:
- \( P(0) \) is true, and
- \( P(n) \rightarrow P(n+1) \)
The template for induction proofs is:
- Define a predicate \( P(n) \)
- Prove that \( P(0) \) is true
- Prove that \( P(n) \rightarrow P(n+1) \)
Example: Sum of natural numbers
Prove the theorem:
\[\sum_{i=1}^{n} i = \frac{n(n+1)}{2}
\]
Proof: let \( P(n) \) be the predicate \( \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)
Base case: \( P(0) \) is true
Inductive step: assume \(P(n) \)
\[1 + 2 + … + n = \frac{n(n+1)}{2}
\]
to prove \(P(n+1) \)
\[1 + 2 + … + n + (n+1) = \frac{(n+1)(n+2)}{2}
\]
Now, adding \( (n+1) \) to both sides of the first equation and doing the math gives exactly the second equation:
\[\begin{align}
1 + 2 + … + n + (n+1) & = \frac{n(n+1)}{2} + (n+1)\\
& = \frac{n^2 + 3n + 2}{2} \\
& = \frac{(n+1)(n+2)}{2}
\end{align}
\]
Therefore, if \( P(n) \) is true (by assumption), then so is \(P(n+1) \)
Remarks:
1. The basic plan for proving the valdity of any implication is: assume the LHS and then prove the RHS. We don’t know and don’t care if \( P(n) \) is true; we assume that is true bcause all we care about is the relationship \( P(n) \rightarrow P(n+1) \).
2. We found out by syntactical manipulations that \( P(n) \) is equivalent to \(P(n+1) \), and since \( P(n) \) is true (by assumption), then so is \(P(n+1) \)
3. And we do have a base case to start the induction with. That’s all there is.
High-level strategy: we’ve shown that \( P(n) \) is equivalent to \( P(n+1) \).
Example: A Divisibility Theorem
Prove that
\[3 \mid (n^3 – n )
\]
That is, \( (n^3 – n ) \) is a multiple of 3.
We define \( P(n) \) as \( (n^3 – n ) \), and we see that \( P(0) \) is clearly true. For the inductive step, we assume
\[3 \mid (n^3 – n )
\]
to prove \( P(n+1) \)
\[3 \mid ((n+1)^3 – (n+1) )
\]
Multiplying out the second expression yields
\[\begin{align}
3 \mid ((n+1)^3 – (n+1)) & = 3 \mid (n^3 + 3n^2 + 3n + 1 -n -1) \\
& = 3 \mid (n^3 + 3n^2 + 2n)
\end{align}
\]
Now, the last expression is equal to \( n^3 – n \), which is multiple of 3 by assumption, plus \( 3n^2 + 3n \), which is a multiple of 3 as well. Therefore, \( P(n+1) \) is true.
The clean proof would then be:
Proof: Let \( P(n) \) be \( (n^3 – n ) \)
Base case: \( P(0) \) is true because \( 3 \mid 0^3 -0 \)
Inductive step: Assume \( P(n) \) is true, then
\[\begin{align}
3 \mid n^3 – n & \rightarrow 3 \mid (n^3 – n) + 3(n^2 + n) \\
& \rightarrow 3 \mid n^3 + 3n^2 + 3n + 1 – n -1 \\
& \rightarrow 3 \mid (n+1)^3 – (n + 1)
\end{align}
\]
Again, the first implication is true because of assumption plus a multiple of 3. The second implication is just a rewrite of the first one using hints from out scatchwork from before (the plus one minus one trick); and the third implication is \( P(n+1) \), so we have proved that \( P(n) \) implies \( P(n+1) \).
High-level strategy: we’ve shown that \( P(n) \) implies something obviously true, and that something is equivalent to \( P(n+1) \).
Example: an incremental algorithm
That is, \( y \rightarrow y + 1\)
Increment(y)
if y = 0 then return(1) else
if (y mod 2) = 1 then
return(2 · Increment(⌊y/2⌋))
else return(y + 1)
Our induction hypothesis is \( Increment(y) \rightarrow y + 1 \); the case off y = 0 and y being even are clearly correctly handled.
The case of odd y (i.e. \(y = 2m + 1 \) for some integer m) can be dealt with:
\[\begin{align}
2 \times Increment( (⌊2m + 1)/2⌋ ) &= 2 \times Increment( ⌊m + \frac{1}{2}⌋ ) \\
& = 2 \times Increment(m) \\
& = 2(m+1) \\
& = 2m + 2 = y + 1
\end{align}
\]