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:

1. Define a predicate $$P(n)$$
2. Prove that $$P(0)$$ is true
3. 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}