CIS-375 Help Session Note 5 (Spring 2020)

02 Apr 2020

Justifying mathematical induction
Strong Induction
- What does the Fibonacci proof imply?
Mathematical induction done wrong
Sample Q&A

Scire ad trascendere - Learn to transcend.

Topics covered:

Mathematical induction
Strong induction

Justifying mathematical induction

Mathematical induction is a very powerful tool for proving integer-related propositions. Since they are integer related, we can denote a particular proposition by $P(n)$. For example, we let

\[P(n): \quad 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.\]

This proposition asserts that the sum of consecutive integers from 1 to $n$ equals to $n(n+1)/2$. We can look at some specific cases of $P(n)$, for example,

\[\begin{align*} P(1):\quad & 1 = \frac{1 \times 2}{2}\\ p(2):\quad & 1 + 2 = \frac{2 \times 3}{2}, \end{align*}\]

and they all seem to be true. It would be really great if we can prove that $P(n)$ is always true for all integers greater than or equal to 1, because then we can compute the sum of (a large number of) consecutive integers with three operations only: one addition, one multiplication and one division, which is much more convenient!

I am going to show you how to prove this proposition with mathematical induction first, and then explain the secret behind it.

Prove the following proposition is true for $n \geq 1$ with mathematical induction.

\[P(n): \quad 1 + 2 + \cdots + n = \frac{n(n+1)}{2}.\]

We prove this by induction on $n$.

Basis: when $n=1$, $P(1)$ is true.

Induction hypothesis: Suppose $P(k)$ is true for some $k \geq 1$. That is, we assume

\[\begin{align}\label{box1-1} 1 + 2 + \cdots + k = \frac{k(k+1)}{2} \end{align}\]

is true.

Induction step: We need to prove that $P(k+1)$ is true. More concretely, we would like to prove

\[\begin{align}\label{box1-2} 1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2} \end{align}\]

Now, we need to find a way to derive Equation $\ref{box1-2}$ using $\ref{box1-1}$. We can observe that if we add $(k+1)$ to both sides of $\ref{box1-1}$, we would have

\[\begin{align}\label{box1-3} 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1). \end{align}\]

It is obvious that this equality is true. The left hand side of Equation $\ref{box1-3}$ is identical to Equation $\ref{box1-2}$’s, which means we are very close to our objective. As long as we can show the right hand side of $\ref{box1-3}$ is the same as the right hand side of $\ref{box1-2}$, we would be able to prove that Equation $\ref{box1-2}$ and $\ref{box1-3}$ are essentially the same, which implies $\ref{box1-2}$ is also true.

The RHS of Equation $\ref{box1-3}$ writes

\[\begin{align*} \mbox{RHS} &= \frac{k(k+1)}{2} + (k+1)\\ &= \frac{k(k+1) + 2(k+1)}{2}\\ &= \frac{(k+1)(k + 2)}{2}, \end{align*}\]

which is exactly the same as RHS of Equation $\ref{box1-2}$. Therefore, we have shown that $P(k+1)$ is true. By the principle of mathematical induction, $P(n)$ is true for $n \geq 1$.

The bolded text indicates there are three key steps of mathematical induction (MI): base step (basis), induction hypothesis (IH) and induction step (IS).

In basis, we show $P(n_0)$ is true for some natural number $n_0$.
In IH, we assume $P(k)$ is true for some integer $k \geq n_0$.
In IS, we show that $P(k+1)$ is true using the hypothesis in IH.

If we are able to complete these three steps, by the principle of MI, the proposition is true for all integers that are greater than or equal to $n_0$.

So, we have only completed three steps, but why this little effort can help us justify $P(n)$ is true for infinite amount of $n$’s? The underlying mechanism of MI proof above can be illustrated as below:

\[{\large P(1) \rightarrow P(2) \rightarrow P(3) \rightarrow \cdots \rightarrow P(m) \rightarrow \cdots }\]

In the base case, we have shown that $P(1)$ is true.
In IH and IS, if we let $k=1$, then we know “if $P(1)$ is true, then $P(2)$ is true”. Since $P(1)$ is indeed true, we know that $P(2)$ is true.
In IH and IS, if we let $k=2$, then we know “if $P(2)$ is true, then $P(3)$ is true”. Since $P(2)$ is indeed true, we know that $P(3)$ is true.

It is not difficult to see this “chain” of reasoning goes on indefinitely. Therefore for any $m \geq 1$, we would be able to prove $P(m)$ is true.

Why is mathematical induction worth mentioning in this lecture? In my opinion, it is special because in IH and IS, you can make use of your proposition as if it is true! Usually, before being rigorously proven, a proposition is merely a “conjecture”, and it should never be used in any proof. However, the method of mathematical induction is so well designed that you can write a rigorous proof using unproven results. A (possibly bad) analogy is that mathematical induction is similar to proof by contradiction. In both methods, you assume something is true, which gives you more resources to work with.

Remarks:

Base case is vital: it is the foundation of your proof, for the “chain” starts there. As you will see later, a faulty basis will render your proof completely meaningless.
This also shows why we are proving $P(k+1)$ is true in the IS instead of, say $P(k+2)$ is true. If you choose to prove $P(k+2)$ is true in the IS, then some numbers will be skipped in the “chain”. Now you cannot show the proposition is true for all integer greater than or equal to the basis. However, if you have proved $P(k+2)$ is true, it is equivalent to showing the proposition being true for all odd/even integers that are greater than or equal to the basis.
The MI format in the textbook does not require you to write “induction step” explicitly. Just keep in mind that this is an essential part of the process.

Strong Induction

Strong induction is very similar to the original version of induction, except that the IH is different. In strong induction, we do the following:

In basis, we show $P(n_0)$ is true for some natural number $n_0$.
In IH, we assume $P(n_0), P(n_0 + 1), P(n_0 + 2), \ldots, P(k)$ are all true for some integer $k \geq n_0$.
In IS, we show that $P(k+1)$ is true using the hypothesis in IH.

If we are able to complete these three steps, by the principle of MI, the proposition is true for all integers that are greater than or equal to $n_0$.

Strong induction has a stronger assumption, because we hypothesize all cases before $k$ are true. It is particularly useful when proving $P(k+1)$ is true requires multiple other cases between $P(n_0)$ and $P(k+1)$ to be true.

The Fibonacci numbers are the list of integers $0, 1, 1, 2, 3, 5, \ldots$ where $F_0=0$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n \geq 2$. Prove that every positive integer can be expressed as a sum of distinct Fibonacci numbers.

The proposition can be written as:

$P(n)$: $n$ can be represented as the sum of distinct Fibonacci numbers.

Basis: $P(1)$ is true because $1 = 0 + 1$.

IH: Suppose $P(1), P(2), \ldots, P(k)$ are all true for some $k \geq 1$.

IS: We need to show $P(k+1)$ is true, which means $k+1$ can be written as the sum of Fibonacci numbers. For the number $k+1$, there are two possibilities:

If $k+1$ is a Fibonacci number itself, it can be wriiten as $k+1 = 0 + (k+1)$, which is the sum of two distinct Fibonacci numbers.
If $k+1$ is not a Fibonacci number, we can look ahead and find the largest Fibonacci number that is less than $k+1$, which is denoted by $F_r$. We can also look behind and find the smallest Fibonacci number that is greater than $k+1$, which is denoted by $F_{r+1}$. Now we can assume $k+1=F_r + j$. Because $k+1 \geq 2$, we know that $r \geq 2$. Therefore, we can write
\[\begin{align*} F_{r+1} = F_{r-1} + F_{r} &> k+1 = F_r + j\\ F_{r-1} &> j. \end{align*}\]
That is, $j < F_{r-1} \leq F_r$. Because $1 \leq j < F_{r-1}$, according to the IH, it can be represented as the sum of distinct Fibonacci numbers. Since $j < F_r$, we know that $F_r$ must not be a member of the sum. Therefore, $k+1 = F_r + j$ is the sum of distinct Fibonacci numbers.

It can be seen that $P(k+1)$ is true. By the principle of strong induction, we can conclude that the $P(n)$ is true for $n \geq 1$.

What does the Fibonacci proof imply?

In the example above, we use strong induction to show that every positive integer can be expressed as a sum of distinct Fibonacci numbers. The idea of proof is simple: given a new number $k+1$, if it is a Fibonacci number, than it can be easily written as the sum of distinct Fibonacci numbers. If not so, then I just find the previous Fibonacci number $F_r$ and the offset from $F_r$ to $k+1$ (denoted by $j$). Because $j$ has been already written as the sum of distinct Fibonacci numbers without using $F_r$, we know that $k+1 = F_r + j$ is the sum of distinct Fibonacci numbers. Although we are trying to prove whether this statement is true or not, you may have realized that this idea provides an exact way to find out what Fibonacci numbers are needed to add up to a particular integer! We can summarize the idea into the following algorithm:

\begin{algorithm}
\begin{algorithmic}

\PROCEDURE{find-representation}{$n$}

  \IF{$n$ is Fibonacci}
    \RETURN $[0, n]$ \COMMENT{$n = 0 + n$}
  \ELSE
     \STATE find the previous Fibonacci number $F_r$
     \RETURN $[F_r]$ + \CALL{find-representation}{$n - F_r$}
  \ENDIF

\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}

The corresponding Python implementation is shown as below.

Mathematical induction done wrong

I think it is also important to show you how not to use MI correctly. As I said, MI allows you to write a proof with unproven results, which makes the method error-prone. The worst part is that these error can be very subtle. In this section, I want to show you how tricky these mistakes can be, and how they turn your proof completely invalid.

Prove the following proposition is true for $n \geq 1$ with MI.

$P(n)$: If a group has $n$ people, then they all have the same name.

Basis: $P(1)$ is clearly true.

IH: Assume $P(k)$ is true, i.e. the group of $k$ people has the same name.

IS: We need to prove $P(k+1)$ is true. Suppose we put all $k+1$ people in a line.

Consider the first $k$ people, because $P(k)$ is true, their names are the same.
Consider the last $k$ people, because $P(k)$ is true, their names are the same.
Because first $k$ people and last $k$ people overlaps, it is obvious that the names of all $k+1$ people are the same.

Therefore, $P(n)$ is true for $n \geq 1$ by mathematical induction.

Hover to show why it's wrong.

When you go from $P(1)$ to $P(2)$ ($k=1$), the first $k$ people does not overlap with the last $k$ people. Therefore, these two group of people can have different names, and the proof breaks down here.

Prove the following proposition is true for $n \geq 0$ with strong induction.

\[P(n): 2n = 0\]

Basis: $P(0)$ is clearly true.

IH: Assume $P(0), P(1), P(2), \ldots, P(k)$ are true for some $k \geq 0$.

IS: We need to prove $P(k+1)$ is true. We can write $k+1 = i + j$, where $i, j \geq 0$. It can be seen that

\[2(k + 1) = 2(i + j) = 2i + 2j.\]

Because $P(i)$ and $P(j)$ are both true, we know that $2(k+1)=0$. Therefore, $P(k+1)$ is true. By the principle of MI, $P(n)$ is true for $n \geq 0$.

Hover to show why it's wrong.

We rewrite $k+1$ as $k+1 = i + j$ and assume $P(i)$ and $P(j)$ are both true in the IS. When $k=0$, we need to prove $P(k+1=1)$ is true. The only way to rewrite $1$ is $1=0+1$, that is, $i=0$, $j=1$ (or reversed), but we assume $P(i)$ and $P(j)$ are both true! That is to say, the error is we assume $P(1)$ is true when we need to prove $P(1)$.

These invalid proofs should serve as an reminder to take extra care with MI proofs. Here, they try to use MI to prove obviously ridiculous propositions, as to imply something is wrong. However, in reality, you may need to use MI to prove something whose validity has never been verified. It is very difficult, yet also important to make sure that you do not fall for similar mistakes in your proof.

Sample Q&A

Let $n$ be a positive integer. Prove, by mathematical induction, that the following equation is true for all $n$.

\[1 + 5 + 9 + \cdots + (4n-3) = \frac{(4n-2)n}{2}\]

We know that

\[P(n): 1 + 5 + 9 + \cdots + (4n-3) = \frac{(4n-2)n}{2}.\]

It would be really important to know that every single case of $P(n)$ actually means. For example:

\[\begin{align*} P(1):& 1 = \frac{2\times 1}{2}\\ P(2):& 1 + 5 = \frac{6 \times 2}{2}\\ P(3):& 1 + 5 + 9 = \frac{10 \times 3}{2}\\ &\vdots \end{align*}\]

It is not difficult to verify that $P(1)$, $P(2)$ and $P(3)$ are all true.

Basis: when $n=1$, $P(1)$ is true.

IH: suppose $P(k)$ is true for some $k \geq 1$. That is,

\[\begin{align}\label{qa1-eq1} 1 + 5 + 9 + \cdots + (4k-3) = \frac{(4k-2)k}{2}. \end{align}\]

IS: we need to prove that $P(k+1)$ is true. We know that $P(k+1)$ is

\[\begin{align}\label{qa1-eq2} 1 + 5 + 9 + \cdots + (4k-3) + (4k + 1) = \frac{(4k+2)(k+1)}{2}. \end{align}\]

Because of the IH, Equation $\ref{qa1-eq1}$ is true. It is obvious that if we add the same quantity to both sides of an equality, the equality still holds. If we compare Equation $\ref{qa1-eq1}$ and $\ref{qa1-eq2}$, we would see that there is an extra $(4k+1)$ term on the LHS of $\ref{qa1-eq2}$. Therefore, it would be nice to see what happens if we add $(4k+1)$ to both sides of Equation $\ref{qa1-eq1}$. Remember that after this operation, the resulting equality will still be true. The addition yields

\[\begin{align}\label{qa1-eq3} 1 + 5 + 9 + \cdots + (4k-3) + (4k+1) = \frac{(4k-2)k}{2} + (4k+1), \end{align}\]

which is an equality that holds true. The left hand side of Equation $\ref{qa1-eq3}$ is completely identical to $\ref{qa1-eq2}$. For the RHS of $\ref{qa1-eq3}$, if we combine all the terms together, we will have

\[\begin{align*} &\phantom{=}\frac{(4k-2)k}{2} + (4k+1)\\ &= \frac{(4k-2)k + 2(4k+1)}{2}\\ &= \frac{(4k+2)(k+1)}{2}, \end{align*}\]

which is completely identical to the RHS of $\ref{qa1-eq2}$. Now we have shown that Equation $\ref{qa1-eq3}$ is essentially the same as $\ref{qa1-eq2}$. Because Equation $\ref{qa1-eq3}$ is true, $\ref{qa1-eq2}$ is also true. Therefore, $P(k+1)$ holds.

By the principle of MI, $P(n)$ holds true for $n \geq 1$.

Let $n$ be a positive integer. Prove, by mathematical induction, that the following equation is true for all $n$.

\[1 + 2 + 3 + \cdots + (2n-1) + 2n > 2n^2.\]

We know that

\[P(n): 1 + 2 + 3 + \cdots + (2n-1) + 2n > 2n^2.\]

It would be really important to know that every single case of $P(n)$ actually means. For example:

\[\begin{align*} P(1):& 1 + 2 > 2 \cdot 1^2 \quad(n=1,2n=1)\\ P(2):& 1 + 2 + 3 + 4 > 2 \cdot 2^2\quad(n=2,2n=4)\\ P(3):& 1 + 2 + 3 + 4 + 5 + 6 > 2 \cdot 3^2\quad(n=3,2n=6)\\ &\vdots \end{align*}\]

It is not difficult to verify that $P(1)$, $P(2)$ and $P(3)$ are all true.

Basis: when $n=1$, $P(1)$ is true.

IH: suppose $P(k)$ is true for some $k \geq 1$. That is,

\[\begin{align}\label{qa2-eq1} 1 + 2 + 3 + \cdots + (2k-1) + 2k > 2k^2. \end{align}\]

IS: we need to prove that $P(k+1)$ is true. We know that $P(k+1)$ is

\[\begin{align}\label{qa2-eq2} 1 + 2 + 3 + \cdots + (2k-1) + 2k + (2k+1) + 2(k+1) > 2(k+1)^2. \end{align}\]

Because of the IH, Equation $\ref{qa2-eq1}$ is true. It is obvious that if we add the same quantity to both sides of an inequality, the inequality still holds. If we compare Equation $\ref{qa2-eq1}$ and $\ref{qa2-eq2}$, we would see that there are two extra terms on the LHS of $\ref{qa2-eq2}$. If we add those two terms to both sides of Equation $\ref{qa2-eq1}$, we would have

\[\begin{align}\label{qa2-eq3} 1 + 2 + 3 + \cdots + (2k-1) + 2k + (2k+1) + 2(k+1) > 2k^2 + (2k+1) + 2(k+1). \end{align}\]

If we simplify the RHS of $\ref{qa2-eq3}$, we would have

\[\begin{align*} 2k^2 + (2k+1) + 2(k+1) = 2k^2 + 4k + 3. \end{align*}\]

If we simplify the RHS of $\ref{qa2-eq2}$, we would have

\[\begin{align*} 2(k+1)^2 = 2(k^2 + 2k + 1) = 2k^2 + 4k + 2. \end{align*}\]

Therefore, based on $\ref{qa2-eq3}$, we can write

\[\begin{gather*} 1 + 2 + 3 + \cdots + (2k-1) + 2k + (2k+1) + 2(k+1) > 2k^2 + (2k+1) + 2(k+1)\\ 1 + 2 + 3 + \cdots + (2k-1) + 2k + (2k+1) + 2(k+1) > 2k^2 + 4k + 3 > 2k^2 + 4k + 2\\ 1 + 2 + 3 + \cdots + (2k-1) + 2k + (2k+1) + 2(k+1) > 2(k+1)^2, \end{gather*}\]

which indicates $\ref{qa2-eq2}$ is true. That is, $P(k+1)$ is true.

By the principle of MI, $P(n)$ holds true for $n \geq 1$.

Prove the following inequality by mathematical induction, where $n$ is a positive integer.

\[\begin{align*} 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^n} \geq 1 + \frac{n}{2}. \end{align*}\]

The proposition can be written as

\[\begin{align*} P(n): 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^n} \geq 1 + \frac{n}{2}. \end{align*}\]

Basis: when $n=1$, it can be seen that

\[\begin{align*} P(1): 1 + \frac{1}{2^1} \geq 1 + \frac{1}{2} \end{align*}\]

is true.

IH: suppose $P(k)$ is true for some integer $k \geq 1$. That is, we assume

\[\begin{align}\label{q2a-1} P(k): 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^k} \geq 1 + \frac{k}{2} \end{align}\]

is true.

IS: we need to show $P(k+1)$ is true.

What is $P(k+1)$?
\[\begin{align}\label{q2a-2} P(k+1): 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^k} + \frac{1}{2^k + 1} + \frac{1}{2^k + 2} + \cdots + \frac{1}{2^{k+1}} \geq 1 + \frac{k+1}{2} \end{align}\]
Given that $2^{k+1} = 2 \cdot 2^k = 2^k + 2^k$, how many terms are inside the following equation?
\[\frac{1}{2^k + 1} + \frac{1}{2^k + 2} + \cdots + \frac{1}{2^{k+1}}\]
There should be $2^k$ terms! That is to say, $P(k+1)$ contains $2^k$ more terms on LHS compared to $P(k)$.
Which term is the smallest among these $2^k$ terms?

The term with the greatest denominator is $\frac{1}{2^{k+1}}$. Therefore, it is the smallest. As a result, we have
\[\frac{1}{2^k + 1} + \frac{1}{2^k + 2} + \cdots + \frac{1}{2^{k+1}} \geq \underbrace{\frac{1}{2^{k+1}} + \frac{1}{2^{k+1}} + \cdots + \frac{1}{2^{k+1}}}_{2^k~\mbox{terms}} = 2^k \cdot \frac{1}{2^{k+1}} = \frac{1}{2}.\]

With the hints above, try to form a proof!

Let $A_1, A_2, \ldots, A_n$ be sets ($n \geq 2$). Suppose for any two sets $A_i$ and $A_j$, either $A_i \subseteq A_j$ or $A_j \subseteq A_i$. Prove, by mathematical induction, that one of these $n$ sets is a subset of all of them.

The proposition can be written as

\[\begin{align*} P(n): \mbox{if there are $n$ such sets, then one of them is a subset of all $n$ sets.} \end{align*}\]

Basis: when $n=2$, there are two sets $A_1, A_2$, where either $A_1 \subseteq A_2$ or $A_2 \subseteq A_1$ is true. Because $A_1 \subseteq A_1$ and $A_2 \subseteq A_2$ are always true, in both cases mentioned before, there will always be a set that is the subset of $A_1$ and $A_2$ at the same time. Therefore, $P(2)$ is true.

IH: suppose $P(k)$ is true for some integer $k \geq 2$. That is to say, there exists a set $A_s$ among these $k$ sets, where $A_s$ is the subset of all $k$ sets. More concretely, $A_s \subseteq A_i$ is true for $i = 1, 2, \ldots, k$.

IS: we need to show $P(k+1)$ is true. In case $k+1$, we introduce a new set $A_{k+1}$ that accords with the constraints given by the question. For $A_s$ and $A_{k+1}$, either one of these two holds:

$A_s \subseteq A_{k+1}$ holds. Now, is there a set that is the subset of all $k+1$ sets? What is it?
$A_{k+1} \subseteq A_s$ holds. Now, is there a set that is the subset of all $k+1$ sets? What is it?

With the hints above, try to form a proof!

Present a proof, via mathematical induction, to conclude that the following theorem is true:

Theorem (Fundamental theorem of arithmetic) Every positive integer that is greater than 1 is a product of prime numbers.

The proposition can be written as

\[\begin{align*} P(n): \mbox{$n$ can be written as the product of prime numbers}. \end{align*}\]

For clarity, we allow number $a$ to be the product of $a$ itself.

Basis: when $n=2$, 2 is prime, which is the product of prime. Therefore, $P(2)$ is true.

IH: (strong induction) suppose $P(2), P(3), \ldots, P(k)$ are all true for some integer $k \geq 2$. That is, $2, 3, \ldots, k$ can be represented as the product of primes, respectively.

IS: we need to show that $P(k+1)$ is true. That is, we need to prove that $k+1$ can be written as the product of primes. For the number $k+1$, there can only be two possibilities:

If $k+1$ is prime, then it is product of prime.
If $k+1$ is not prime, then it can be written as the product of two smaller integers, i.e. $k+1 = c\cdot d$. How do you show $k+1$ is product of prime?

With the hints above, try to form a proof!

Alan Xiang's Blog

CIS-375 Help Session Note 5 (Spring 2020)

Justifying mathematical induction

Strong Induction

What does the Fibonacci proof imply?

Mathematical induction done wrong

Sample Q&A