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

\]