4 Proof by induction

We have seen several type of proofs so far:

  • direct proof (sometimes known as deductive proof);

  • proof by case analysis;

  • proof by contradiction;

  • proof using the contrapositive.

In this chapter, we introduce a new type of proof, called proof by induction.

Proof techniques:

Let n_0 \in \mathbb{Z}_+ and let P(n) be a statement for n\geq n_0. A proof by induction is where one prove that:

  • P(n_0) is true, and

  • P(n) \implies P(n+1) for all n\geq n_0.

Combining these two statements, by the principle of induction, we deduce that P(n) is true for all n\geq n_0.

Etymology:

The word induction comes from the Latin in and ductus meaning “to lead”. An inductive proof is one where a starting case leads into the next case and so on.

(In contrast, deduction has the prefix de meaning “down from”. When we do a proof by deduction, we start from certain rules and truths that “lead down” to specific things that must follow as a consequence.)

Example:

Statement: Show that, for every n\in\mathbb{Z}_+, we have 1+2+3+\cdots+n=\sum_{i=1}^n=\frac{n(n+1)}{2}.

Proof: For n\in\mathbb{Z}_+, let P(n) be the following statement. 1+2+3+\cdots+n=\frac{n(n+1)}{2}. We will show that P(n) is a true statement, for all n\in\mathbb{Z}_+ by giving a proof by induction.

First, let us consider P(1). We have 1=\frac{1(1+1)}{2}, hence, P(1) holds.

Now, suppose that P(k) is true for some positive integer k, that is 1+2+3+\cdots+k=\frac{k(k+1)}{2}.
Then \begin{align*} 1+2+3+\cdots+k+(k+1)&=\frac{k(k+1)}{2}+(k+1)\\ &=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}\\ &=\frac{k^2+3k+2}{2}\\ &=\frac{(k+1)(k+2)}{2}. \end{align*} This shows that if P(k) is true then P(k+1) is true. By the Principle of Mathematical Induction, it follows that P(n) is true for all natural numbers n.

\square

It is not enough to show P(n)\implies P(n+1), we need to also show P(n_0) holds. As we saw in the above example, we often have that n_0=1. However, this is not always the case. The following example highlights these two points.

Example:

Let P(n) be the statement n^2\leq 2^{n-1}. To highlight the importance of the base case, let us first show that for n\geq 3 we have P(n) \implies P(n+1).

Suppose that P(k) is a true statement for some natural number k\geq 3, that is k^2\leq 2^{k-1}.

Then

If we set n_0=1, we do have P(1) holds (since 1\leq 1), but have not proven P(1) \implies P(2) (since 1\not\geq 3). In fact, we can not prove P(1) \implies P(2) since P(2) is false (2^2\not\leq 2^1).

Since we have shown that for n\geq 3 we have P(n) \implies P(n+1), we might want to set n_0=3. However, P(3) is also false since 3^2\not\leq 2^2. In fact, we can check that P(3), P(4), P(5) and P(6) are all false. However, P(7) is true since we have that 7^2=49\leq 64 = 2^6.

Therefore, we have n_0=7 and by the Principle of mathematical induction, we have shown that n^2\leq 2^{n-1} for all n\in\mathbb{Z}_+ such that n\geq 7.

Sometimes, the principle of induction is not strong enough, either because we need more than one base case, or because to prove P(n) is true we need to know P(m) is true for some unknown m<n. This is where we can use the strong principle of mathematical induction.

Proof techniques:

Let n_0 \in \mathbb{Z}_+ and let P(n) be a statement for n\geq n_0. A proof by strong induction is where one prove that:

  • P(n_0), P(n_0+1),\dots P(n_0+k) is true (for some k\geq 0), and

  • for all n\geq n_0+k, show that P(i) is true for all i\leq n \implies P(n+1) is true.

Combining these two statements, by the principle of induction, we deduce that P(n) is true for all n\geq n_0.

Example:

Statement: Suppose that x_1 = 3 and x_2 = 5 and for n \geq 3, define x_n = 3x_{n-1} -2x_{n-2}. Show that x_n = 2^n + 1, for all n\in\mathbb{Z}_+.

Proof: Let P(n) be the statement “x_n= 2^n+1”. We will show that P(n) is a true statement, for all n\in\mathbb{Z}_+, by giving a proof by induction. First, we consider our base cases n_0=1 and n_{0+1}=2. We have the given initial conditions x_1=3 and x_2=5. Using the formula x_n=2^n+1, we indeed have x_1= 2^{1}+1=3 and x_2= 2^2+1= 5.Therefore, P(1) and P(2) hold.

Let n\in\mathbb{Z}_+ and suppose for all i\in \mathbb{Z}_+ such that i \leq n we have P(n) holds. Then by our assumption x_{n-1}= 2^{n-1}+1 and x_n = 2^n +1. We have: This shows that if P(i) is true, for 1\leq i\leq n, then P(n+1) is true. By the Strong Principle of Mathematical Induction, it follows that P(n) is true for all natural numbers n. \square
Example:

Statement: Show that every natural number can be written as the sum of distinct powers of 2. That is for all n\in\mathbb{Z}_+, we can write n=2^{a_1}+2^{a_2}+\dots+2^{a_r} with a_i \in \mathbb{Z}, a_i\geq 0, and a_i\neq a_j if i\neq j.

Proof: Let P(n) be the statements “there exists a_1,\dots a_r \in \mathbb{Z} such that a_i\geq0, a_i\neq a_j if i\neq j and n=2^{a_1}+2^{a_2}+\dots+2^{a_r}”. We check that our base case n_0=1 is true. Indeed 1=2^0 so P(1) holds.

Let n\in\mathbb{Z}_+ and suppose for all i\in \mathbb{Z}_+ such that i \leq n we have P(n) holds. Consider A = \{n+1-2^\ell: \ell\in\mathbb{Z}_{>0} \wedge n+1-2^\ell\geq 0\}. We note that A \subseteq \mathbb{Z}_{\geq 0} by definition. Taking \ell = 1, we see that n-1\in A, so A \neq \emptyset. So, by the Well Ordering Principle, A has a minimal element, call it m. If m=0 then n+1 = 2^\ell and P(n+1) holds. If m\neq 0, then since P(m) holds, we have there exists a_1,\dots a_r \in \mathbb{Z} such that a_i\geq0, a_i\neq a_j if i\neq j and m=2^{a_1}+2^{a_2}+\dots+2^{a_r}. Then n+1 = 2^\ell+2^{a_1}+2^{a_2}+\dots+2^{a_r}, so we just need to show \ell \neq a_i for all i. For a contradiction, suppose \ell = a_i for some i. Then n+1 \geq 2^\ell+2^\ell = 2^{\ell+1}, so 0\leq n+1-2^{\ell+1}<m which contradicts the definition of m. Therefore the powers are distinct and P(n+1) holds.

Therefore, by the principle of strong induction, we have showed that every natural number can be written as the sum of distinct powers of 2.

Remark:

A proof by induction is a special case of a proof by strong induction (taking k=0)! We present these two ideas separately as it is easier to understand induction before understanding strong induction. However, most mathematician will say “induction” to mean both induction and strong induction and do not distinguish between the two (so feel free to also not distinguish between the two).