Mathematical Induction

Introduction

There are numerous prove techniques used to prove a statement. However, mathematical induction has wide applicability in computer science.

• How it works
  • Example
  • Arithmetic-Sum formula example
  • Prove log algorithm
  • Recurrence Equation

How it works

Let $P(n)$ be a predicate. We need to prove that for all integers $n \ge 1$, $P(n)$ is true. We can accomplish the proof by induction as follows.

1. (Induction Base) Prove $P(1)$ is true
2. (Induction Step) Prove that $\forall n \ge 1$,
   $$P(n) \implies P(n+1)$$

The anology is similar to that of dominoes. Suppose they are aranged close together such that if you knock out block 1, then it will knock out block2 and so on and on....

Example

use induction to prove that all integers of the type

are divisible by 3, for all integers $n \ge 1$

Proof :

1. for the base case, P(1) = 4-1 = 3, which is indeed divisble by three
2. now suppose for some $n \ge 1$,
   $$P(n) = 4^n-1 \text{ is divisible by three} \quad \text{(This is the hypothesis)}$$
   We will prove that will imply that
   $$P(n+1) = 4^{n+1}-1 \text{ is also divisible by three} \quad \text{(This is the conclusion)}$$
3. Now to prove the conclusion:
   $$p(n+1) = 4^{n+1}-1 = 4*4^n-1 = 4*4^n-4+3 = 4(4^n-1)+3$$
   By hpothesis, $4^n-1$ is divisble 3. So, $4^n-1 = 3k$ for some integer k. So,
   $$P(n+1) = 4*3k+3 = 3(4k+1)$$
4. Therefore, P(n+1) is divisible by three.

Arithmetic-Sum formula example

Use induction to prove the Arithmetic-Sum formula.

Proof:

1. For the base base where n = 1,
   $$S(1) = \frac {1(2)}{2}= 1$$
   so the base is correct.
2. Suppose that for some $n \ge 1$, the formula is correct:
   $$S(n) = 1+2+3+...+n = \frac {n(n+1)}{2} \quad \text{Hypothesis}$$
   we will prove that the formual is also correct for $n+1$:
   $$S(n_1) = 1+2+3...+n+(n+1) = \frac {(n+1)(n+2)}{2}$$
3. To prove the conclusion $S(n+1) = S(n) + (n+1)$
   $$\begin{align*} &= \frac {n(n+1)}{2}+(n+1) \quad \text{By Hypothesis} \\ &= \frac {n(n+1)+2(n+1)}{2} \\ &= \frac {(n+1)(n+2)}{2} \end{align*}$$

Prove log algorithm

def log(n:int)->int:
    p:int = 0
    m:int = n
    while(m > 1):
        p = p+1
        m = m/2
    return p

We want to prove the following program computes and returns $\log_2n$, assuming that the input parameter $n$ is an integer power of 2.

Let $p_k$ and $m_k$ denote the resulting values of the variables $p$ and $k$ after iteration k of the while loop, where $k = 0, 1, 2,...$. Here, $k = 0$ represents the values after the initialization and just before the first execution of the while loop; $k = 1$ represents the values after the first execution of the while loop, and so on.

1. First use induction to prove that after the $k^{th}$ iteration of the while loop,
   $$p_k = k, m_k = \frac {n} {2^k} \quad \text{(Loop Invariant)}$$
   (These relations are called loop-invariant.)
2. Then conclude that the return value of the program is $\log_2n$.

Proof: The induction is on the number of iteration $k$. For the induction base, $k = 0$, the results after the initialization and just before the first iteration is $p_0 = 0$, $m_0 = \frac {n}{2^0} = n$. So the base is correct.

Now suppose after iteration $k$ of the while loop, for some $k \ge 0$,

Then the next iteration will increment $p$ by 1, and divide $m$ by 2. So the result after iteration $k+1$ will be:

This completes the induction proof. So, the Loop Invariant is proved for all $k$. At the end, when the while loop terminates, $m = 1$. So, $p = k$, $1= \frac {n}{2^k}$.

This means $n = 2k = 2p$. Therefore, $p =\log_2n$. And this is the value returned by the program.

Recurrence Equation

Let's consider a recurrence equation

(The symbol $\lfloor \rfloor$ is the floor operation, which rounds down a real number to its nearest integer. For example, $\lfloor 3.28 \rfloor = 3$.)

The following table shows the result of $T(n)$ for values of $n=1,2,3,4,....,16$

Now let us use induction to prove $T(n)$ has the following lower and upper bounds.

proof of the upper bound: Prove by induction on $n$ that

1. in this case, we only need one base case, $n=1$

   $$T(1) = 1 \le 2n-1 = 2 \cdot 1-1 = 1,$$

   so the base is correct

2. Now, to prove the upper bound for any $n \ge 2$, suppose the bound is true for all smaller values of $n$. That is, $T(m) \le 2m-1, \forall m < n$. In particular, for $m = \lfloor \frac {n}{2} \rfloor$, the hypothesis is:

   $$𝑇 (⌊\frac{n}{2}⌋) ≤ 2 ⌊\frac{n}{2}⌋ − 1$$

3. Then,

   $$\begin{align*} &T(n) = 2T(⌊\frac{n}{2}⌋) +1 \quad \text{ Start with the recurrence equation} \\ &≤ 2(2⌊\frac{n}{2}⌋ -1)+1 \quad \text{Use the hypothesis} \\ &≤2(2 \cdot \frac{n}{2}-1)+1 \quad \text{Observe that $⌊\frac{n}{2}⌋ ≤\frac{n}{2}$} \\ &≤2(n-1)+1 \\ &≤2n-1 \end{align*}$$

proof of the lower bound: It is similar to the upper-bound.

Hint: Use the relation $\lfloor \frac {n}{2} \rfloor \ge \frac {n-1}{2}$