How to prove by induction

Mathematical induction is a method to systematically prove that a statement which depends on an integer is true for all values of this integer which are greater than some number. Let us be more precise and call S(n) a statement which involves an integer n (not to be confused with a function of n). An example for such a statement may be:

“If b is a real number greater or equal -1, then $(1+b)^n\geq 1+nb.$ “

If S(n) is this statement, then for example S(5) would be: “If b is a real number greater or equal -1, then $(1+b)^5\geq 1+5b.$ ” Depending on the choice of n, such a statement S(n) may be true or false. In the case of this example, the statement is true for every n which is greater or equal zero. We will prove this below. This fact was noticed by Jakob Bernoulli and the above inequality is named after him. At the end of this post we will furthermore prove the binomial theorem and the convergence of the geometric series with the help of induction.

The induction principle

The general method of induction relies on the following principle: Let S(n) be a statement involving an integer n and let a be some integer value. The statement S(n) is proven to be true for all n greater or equal a if the following two statements are proven:

Base case: The statement S(a) is true.
Induction step: If S(n) is true for some integer n greater or equal a, then S(n+1) is true as well.

The first step, the base case, is easy to understand. If we want to prove that S(n) is true for all n greater or equal a, we should start by showing that S(a) is true. However, the induction step may cause some confusion. Here we do not choose another value for n. Instead we assume that for some unspecified n the statement S(n) is true, and from this assumption we try to deduce that then S(n+1) is also true.

Together the base case and the induction step work like an infinite ladder of proofs. Having proven the base case, we know that S(a) is true. Together with the induction step this implies that S(a+1) is true. This again together with the induction step implies that S(a+2) is true, and so on. Therefore, it is enough to prove the base case and the induction step in order to prove S(n) for all n greater or equal a.

Writing down the proof

As usual, when we write down a proof, we should give it some structure and enough details for the benefit of the person who will try to understand (or correct) it. It depends on the context and the people we are writing for, how much detail and structure is appropriate. In any case it will be helpful to the reader if the method of induction is mentioned somewhere in the proof. A reasonable structure for a proof by induction may look like this:

“We are going to prove by induction that S(n) for all n greater or equal a.”
Proof of the base case S(a).
Proof of the induction step: From S(n) follows S(n+1).
Conclusion: “By the principle of induction, S(n) is true for all n greater or equal a.”

Depending on the conventions in your environment, these steps may be more or less fleshed out. Some people may demand that steps 2 and 3 each have their own structure of a proof, while others will be satisfied to see just the main steps and maybe just a “q.e.d.” or a little box instead of a conclusion sentence.

In the following we give three classical examples for a proof by induction.

First example: Proof of Bernoulli’s inequality

We return to the example from the beginning. Let us prove by induction, that for any real number b which is not smaller than -1, the inequality

$(1+b)^n\geq 1+nb$

is true for all integers n greater or equal zero.

Base case: With n=0 the inequality reads $(1+b)^0\geq 1+0\cdot b.$ As the left- and the right-hand side are both equal to 1, this is true.

Induction step: We assume that $(1+b)^n\geq 1+nb$ is true for some integer n. As b is not smaller than -1, the number (1+b) is either positive or zero. Therefore we can multiply the inequality on both sides with (1+b) and it remains true. In this way we obtain

$(1+b)^n(1+b)\geq (1+nb)(1+b)$

which after some simplification becomes

$(1+b)^{n+1}\geq 1+(n+1)b+nb^2.$

On the right-hand side we notice the term nb² which is always a positive number or zero. Therefore we have $1+(n+1)b+nb^2\geq 1+(n+1)b.$ Combined with the previous inequality, this gives

$(1+b)^{n+1}\geq 1+(n+1)b.$

By the induction principle, this proves the above assertion.

Second example: Proof of the binomial theorem

As a next example we prove the general binomial theorem

$(a+b)^{n}= \sum_{k=0}^{n} \left( \begin{array}{c} n\\ k\\ \end{array} \right) a^{k}b^{n-k}$

by induction for all positive integers n. At some point we will use the relation

$\left(\begin{array}{c} n+1\\ k\\ \end{array}\right)=\left(\begin{array}{c} n\\ k\\ \end{array}\right)+\left(\begin{array}{c} n\\ k-1\\ \end{array}\right)$

which is known as Pascal’s identity. We begin our proof with n=1 as the base case. Due to

$\left(\begin{array}{c} n\\ 0\\ \end{array}\right)=\left(\begin{array}{c} n\\ n\\ \end{array}\right)=1$

we obtain a+b on both sides of

$(a+b)^{1}= \sum_{k=0}^{1} \left( \begin{array}{c} 1\\ k\\ \end{array} \right) a^{k}b^{1-k}$

which is therefore shown to be true. (For the case n=2 we obtain (a+b)²=a²+2ab+b² which is easily verified as well.)

In the induction step, we assume that the binomial relation is true for some n and we multiply both sides of the equation by (a+b):

$(a+b)^{n} = \sum_{k=0}^{n}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k}b^{n-k}\,\,|\,\cdot(a+b)$

which leads to two sums on the right-hand side:

$(a+b)^{n+1} = \sum_{k=0}^{n}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k+1}b^{n-k}+\sum_{k=0}^{n}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k}b^{n-k+1}.$

In the remaining steps we aim for a unification of these to only one sum. At first, we apply a little trick. We split off the first term of one of the sums and the last term of the other one:

$(a+b)^{n+1} = \left(\begin{array}{c} n\\ n\\ \end{array}\right)a^{n+1}b^{n-n}+\sum_{k=0}^{n-1}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k+1}b^{n-k}+\sum_{k=1}^{n}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k}b^{n-k+1}+\left(\begin{array}{c} n\\ 0\\ \end{array}\right)a^{0}b^{n-0+1}\\ = a^{n+1}+\sum_{k=0}^{n-1}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k+1}b^{n-k}+\sum_{k=1}^{n}\left(\begin{array}{c} n\\ k\\ \end{array}\right)a^{k}b^{n-k+1}+b^{n+1}$

We see that now the first sum starts with k=0 and ends with k=n-1. In order to make it fit with the second sum, we re-name the summation parameter such that every k is replaced by k-1. Then both sums start with k=1 and end with k=n. We obtain:

$(a+b)^{n+1} = a^{n+1}+\sum_{k=1}^{n}\left(\begin{array}{c} n\\ k-1\\ \end{array}\right) a^{k}b^{n{-k+1}}+\sum_{k=1}^{n}\left(\begin{array}{c}n\\ k\\ \end{array}\right)a^{k}b^{n-k+1}+b^{n+1}$

At this point, the two sums can be merged to one by use of Pascal’s identity. We obtain:

$(a+b)^{n+1} =a^{n+1}+\sum_{k=1}^{n}\left(\begin{array}{c} n+1\\ k\\ \end{array}\right)a^{k}b^{n-k+1}+b^{n+1}\\ =\sum_{k=0}^{n+1}\left(\begin{array}{c} n+1\\ k\\ \end{array}\right)a^{k}b^{n+1-k}.$

As this is the desired equation with n replaced by n+1, the induction step is complete. This concludes our proof that the equation is true any positive integer.

Third example: Convergenve of the geometric series

Let q be a complex number with |q|<1. We prove that the geometric series converges with

$\sum_{j=0}^{\infty}q^{j}=\frac{1}{1-q}.$

In a first part of the proof, we show by use of induction that for any non-negative integer n we have

$\sum_{j=0}^{n}q^{j}=\frac{1-q^{n+1}}{1-q}.$

In the base case of n=0, this relation is 1=1. (In the case of n=1 it has 1+q on both sides of the equation.)

In the induction step we assume the equation to be true for some n and we add qⁿ⁺¹ on both sides, which leads to:

$\sum_{j=0}^{n+1}q^{j}=\frac{1-q^{n+1}}{1-q}+q^{n+1}=\frac{1-q^{n+1}+q^{n+1}-q^{n+2}}{1-q}=\frac{1-q^{n+2}}{1-q}.$

This concludes the induction step and proves the above equation for all non-negative integers n.

In the second part of the proof, we consider the limit of this equation for n to infinity. In this limit, the left-hand side becomes the geometric series. In order to see what happens on the right-hand side, we notice that because of |q|<1 we have

$\lim_{n\rightarrow\infty}q^{n+1}=0.$

Using this fact, we obtain

$\lim_{n\rightarrow\infty}\frac{1-q^{n+1}}{1-q}=\frac{1}{1-q}=\sum_{j=0}^{\infty}q^{j},$

which concludes our proof.

The induction principle

Writing down the proof

First example: Proof of Bernoulli’s inequality

Second example: Proof of the binomial theorem

Third example: Convergenve of the geometric series

Teilen mit:

Related

Leave a comment Cancel reply