PREFACE

Lecture 12: Induction

• Motivation
  • Example
  • Inductive Reasoning
  • Mathematical Induction
  • Induction proof structure
• Basic Induction
  • example
• Variations on Basic Induction
  • Induction From m Upwards
    • Example
  • Induction Steps ℓ > 1
    • example
  • Strong Induction
    • Example
  • Negative Integers, Backward Induction
    • Idea
    • Example: AM-GM Inequality
• Structural Induction
  • Example: Induction on $Σ^∗$
  • Example 2: Induction on $Σ^∗$
  • Example 3: Induction on $Σ^∗$
  • Example 4: Induction on more complex structures
  • Exercise

Motivation

Recursive datatypes

Describe arbitrarily large objects in a finite way

Recursive functions

Define behaviour for these objects in a finite way

Induction

Reason about these objects in a finite way

Example

Recall the recursive program:

Summing the first n natural numbers:

sum(n):
 if(n = 0): 0
 else: n + sum(n −1)

Another attempt:

sum2(n):
 return n ∗(n +1)/2

Induction proof guarantees that these programs will behave the same.

Inductive Reasoning

Suppose we would like to reach a conclusion of the form

$$P(x) \text{ for all } x \text{( of some type)}$$

Inductive reasoning (as understood in philosophy) proceeds from examples.

E.g. From “This swan is white, that swan is white, in fact every swan I have seen so far is white”

Conclude: “Every Swan is white”

Take Notice

This may be a good way to discover hypotheses.

But it is not a valid principle of reasoning!

Mathematical induction is a variant that is valid.

Mathematical Induction

Mathematical Induction is based not just on a set of examples, but also a rule for deriving new cases of P(x) from cases for which P is known to hold.

General structure of reasoning by mathematical induction:

Base Case [B]: $P(a_1),P(a_2),…,P(a_n)$ for some small set of examples $a_1 … a_n$ (often n = 1)

Inductive Step [I]: A general rule showing that if P(x) holds for some cases $x = x_1,…,x_k$ then P(y) holds for some new case y, constructed in some way from $x_1,…,x_k$.

Conclusion: Starting with $a_1 … a_n$ and repeatedly applying the construction of y from existing values, we can eventually construct all values in the domain of interest.

Induction proof structure

Let P(x) be the proposition that …

We will show that P(x) holds for all x by induction on x.

Base case: $x = …$ :

• P(x): …
• ….
• so P(x) holds.

[Repeat for all base cases]

Inductive case: P(x) implies P(y)

• Assume P(x) holds. That is, ….
• We will show P(y) holds.
• …
• So P(x) implies P(y).

[Repeat for all inductive cases]

Basic Induction

Basic induction is the general principle applied to the natural numbers.

Goal: Show P(n) holds for all $n ∈ \mathbb{N}$.

Approach: Show that:

Base case (B): P(0) holds; and

Inductive case (I): If P(k) holds then P(k + 1) holds.

Conclusion (C): P(n) holds for all $n ∈ \mathbb{N}$.

example

Let $P(n)$ be the proposition that: $\sum_{i=0}^{n} i=\frac{n(n+1)}{2}$

We will show that $P(n)$ holds for all $n ∈ \mathbb{N}$ by induction on n.

[B] Base case: n = 0:

$\sum_{i=0}^{0} i=\frac{0(0+1)}{2}=0$

So P(0) holds.

[I] Inductive case: $P(k) ⇒ P(k +1)$:

That is,

$\sum{i=0}^{k} i= \frac{k(k+1)}{2} \implies \sum{i=0}^{k+1} i=\frac{(k+1)(k+2)}{2}$?

proof:

$$\sum_{i=0}^{k} i = \frac{(k+1)(k+2)}{2} \\ (\sum_{i=0}^{k} i) + (k+1) = \frac{(k+1)(k+2)}{2} + (k+1) \\ \therefore \sum_{i=0}^{k+1} i = (\sum_{i=0}^{k} i) + (k+1) \\ = \frac{k(k+1)}{2} + (k+1) \\ = \frac{k(k+1) + 2(k+1)}{2} \\ = \frac{(k+1)(k+2)}{2}$$

Therefore P(k) implies P(k + 1).

[C] Conclusion: We have P(0) is true, and P(k) implies P(k+1). Therefore, by induction, P(n) holds for all $n ∈ \mathbb{N}$.

Variations on Basic Induction

There are many variants of basic induction that may be more useful in certain circumstances. For example:

1. Induction from m upwards
2. Induction steps >1
3. Strong induction
4. Backward induction
5. Forward-backward induction
6. Structural induction

Induction From m Upwards

$$If \\ [B] \quad P(m)\\ [I] \quad ∀k (≥)m, P(k) → P(k +1) \\ then \\ [C] \quad ∀n(≥)m,P(n)$$

Example

Theorem. For all $n ≥ 1$, the number $8^n −2^n$ is divisible by 6.

[B] $8^1−2^1$ is divisible by 6

[I] if $8^k −2^k$ is divisible by 6, then so is $8^{k+1} − 2^{k+1}$, for all k ≥ 1

Prove [I] using the “trick” to rewrite $8^{k+1}$ as $8 · (8^k − 2^k + 2^k)$ which allows you to apply the IH on $8^k − 2^k$

$$8^{k+1} −2^{k+1} = 8·(8^k −2^k +2^k)−2·2k \\ = 8·(8^k −2^k)+8·2^k −2·2^k\\ = 8·(8^k −2^k)+6·2^k$$

Note we have assume $(8^k −2^k)$ is divisible by 6. Hence the final expression is divisible by 6.

Induction Steps ℓ > 1

$$If \\ [B] \quad P(m)\\ [I] \quad P(k) → P(k +ℓ) \text{ for all } k ≥ m \\ then \\ [C] \quad P(n) \text{ for every } ℓ’th \quad n ≥ m$$

example

The Fibonacci numbers can be defined by the recurrence relation

$$F_1 = 1,F_2 = 1$$

and

$$F_n = F_{n−1} +F_{n−2}, for \quad n > 2$$

The first 12 Fibonacci numbers $F_n$ are:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144

Every 4th Fibonacci number is divisible by 3.

[B] $F_4 =3$ is divisible by 3

[I] if $3 | Fk$, then $3 | F{k+4}$, for all k ≥ 4

Prove [I] by rewriting $F_{k+4}$ in such a way

that you can apply the IH on $F_k$

$$F_{k+4} =F_{k+3} +F_{k+2} \\ =(F_{k+2} +F_{k+1}) + (F_{k+1} +F_{k}) \\ =(F_{k+1} +F_{k}) + 2(F_{k} +F_{k-1}) +F_k \\ =(F_{k} +F_{k-1}) + 4F_{k} + 2F_{k-1} \\ =5F_{k} + 3F_{k-1}$$

Strong Induction

This is a version in which the inductive hypothesis is stronger. Rather than using the fact that P(k) holds for a single value, we use all values up to k.

$$If \\ [B] \quad P(m)\\ [I] \quad [P(m) ∧ P(m+1) ∧ ... ∧ P(k)] → P(k +1) \text{ for all } k ≥ m\\ then \\ [C] \quad P(n), \text{ for all } n ≥ m$$

Example

Claim: All integers ≥ 2 can be written as a product of primes.

[B] 2 is a product of primes

[I] If all $x$ with $2 ≤ x ≤ k$ can be written as a product of primes, then $k +1$ can be written as a product of primes, for all $k ≥ 2$

Proof for [I]?

Proof:

Case 1: $k+1$ is prime.

If k +1 is a prime number, then it is already a product of primes

(since a prime number can be considered a product of itself).

Case 2: $k + 1$ is composite.

If $k +1$ is composite, then it can be written as a product of smaller integers. Assume $k + 1 = a ×b$, where $2 ≤ a, b < k +1$. By the inductive hypothesis, since a and b are less than $k + 1$ and greater than or equal to 2, they can each be written as a product of primes. Thus, $k +1$ can also be written as a product of primes.

Negative Integers, Backward Induction

Take Notice

Induction can be conducted over any subset of $\mathbb{Z}$ with least element. Thus m can be negative; eg. base case $m = -10^6$

One can apply induction in the ‘opposite’ direction $p(m) → p(m−1)$. It means considering the integers with the opposite ordering where the next number after $n$ is $n − 1$. Such induction would be used to prove some $p(n)$ for all $n ≤ m$.

Sometimes one needs to reason about all integers $\mathbb{Z}$. This requires two separate simple induction proofs: one for $\mathbb{N}$, another for $-\mathbb{N}$. They both would start form some initial values, which could be the same, e.g. zero. Then the first proof would proceed through positive integers; the second proof through negative integers.

Idea

To prove $P(n)$ for all $n ≥ k_0$

• verify $P(k_0)$
• prove $P(k_i)$ for infinitely many $k_0 < k_1 < k_2 < k_3 < …$
• fill the gaps

$$P(k_1) → P(k_1 −1) → P(k_1 −2) → ... → P(k_0 +1)\\ P(k_2) → P(k_2 −1) → P(k_2 −2) → ... → P(k_1 +1)$$

Take Notice

This form of induction is extremely important for the analysis of algorithms.

Example: AM-GM Inequality

Theorem. For all $n ≥ 1$,

$$\frac{a_1 +a_2 +...+a_n}{n} ≥ (a_1 ×a_2 ×...×a_n)^{\frac{1}{n}}$$ $$[B] \quad P(2) \\ [Forward Induction] \quad P(k) ⇒ P(2k) \\ [Backward Induction] P(k) ⇒ P(k −1)$$

Base Case P(2)

The AM-GM inequality for two numbers is $\frac{a_1+a_2}{2} ≥ (a_1 a_2)^{\frac{1}{2}}$

This is equivalent to proving $(\frac{a_1+a_2}{2})^2 ≥ (a_1 a_2)$

Expanding the left-hand side:

$$(\frac{a_1+a_2}{2})^2 = \frac{a_1^2 + 2a_1a_2 + a_2^2}{4}$$

Thus, we need to show

$$\frac{a_1^2 + 2a_1a_2 + a_2^2}{4} ≥ a_1a_2$$

Multiplying both sides by 4, we get $a_1^2 + 2a_1a_2 + a_2^2 ≥ 4a_1a_2$, which simplifies to

$$(a_1 − a_2)^2 ≥ 0$$

which is always true. Therefore, the base case holds.

Forward Induction $P(k) ⇒ P(2k)$

Assume that the inequality holds for some n = k, i.e., for any non-negative real numbers $a_1,a_2,··· ,a_k$ , we have:

$$\frac{a_1 +a_2 +...+a_k}{k} ≥ (a_1 ×a_2 ×...×a_k)^{\frac{1}{k}}$$

We now need to prove that the inequality holds for 2k numbers:

$$\frac{a_1 +a_2 +...+a_{2k}}{2k} ≥ (a_1 ×a_2 ×...×a_{2k})^{\frac{1}{2k}}$$

Proof:

Divide the 2k numbers into two groups of k numbers each:

$$G1 =\{a_1,a_2,··· ,a_k\}, G2 = \{a_{k+1},a_{k+2},··· ,a_{2k}\}$$

By the inductive hypothesis P(k), the AM-GM inequality holds for each group:

$$\frac{a_1 +a_2 +...+a_k}{k} ≥ (a_1 ×a_2 ×...×a_k)^{\frac{1}{k}}$$ $$\frac{a_{k+1} +a_{k+2} +...+a_{2k}}{k} ≥ (a_{k+1} ×a_{k+2} ×...×a_{2k})^{\frac{1}{k}}$$

Add these two inequalities:

$$\frac{a_1 +a_2 +...+a_{2k}}{k} ≥ (a_1 ×a_2 ×...×a_{k})^{\frac{1}{k}} + (a_{k+1} ×a_{k+2} ×...×a_{2k})^{\frac{1}{k}}$$

Multiply both sides by $\frac{1}{2}$

Structural Induction

Basic induction allows us to assert properties over all natural numbers. The induction scheme (layout) uses the recursive definition of $\mathbb{N}$.

The induction scheme can be applied not only to natural numbers (and integers) but to any partially ordered set in general especially those defined recursively.

The basic approach is always the same — we need to verify that

• [B] the property holds for all minimal objects — objects that
  have no predecessors; they are usually very simple objects
  allowing immediate verification

• [I] for any given object, if the property in question holds for
  all its predecessors (‘smaller’ objects) then it holds for the
  object itself

Example: Induction on $Σ^∗$

Example 2: Induction on $Σ^∗$

Example 3: Induction on $Σ^∗$

Example 4: Induction on more complex structures

Exercise

---

Welcome to point out the mistakes and faults!