Tutor HuntResources Maths Resources

What Is Proof By Induction?

This article describes what "proof by induction" is and gives an example.

Date : 18/11/2021

Author Information

John

Uploaded by : John
Uploaded on : 18/11/2021
Subject : Maths

Often, we want to prove a result holds for all positive integers n. For example, how do we prove that the sum of numbers from 1 to n is n(n+1)/2?

First, we prove it firsthand for the first case, n=1. (or sometimes, the first couple of cases)

Then, we ASSUME the result holds for some specific but arbitrary n. (or possibly a few adjacent values of n, i.e. n-1, n-2, ...) This is known as weak induction. Alternatively, we can assume the result holds for all values up to n. That would be known as strong induction.

We then prove that, under this assumption, the result holds for n+1. Then since we know the result holds for the base cases, we have proven that the result holds for all values of n, by induction.

Let`s look at an example. How do we prove that the sum of numbers from 1 to n is n(n+1)/2?

The result clearly holds for n=1.

Next, we assume the result holds for n, i.e. the sum of the integers from 1 to n is n(n+1)/2 for this specific n.

Next, the sum of the integers from 1 to n+1 is n(n+1)/2 + (n+1), which is of course equal to (n+1)(n+2)/2.

Therefore, we have proven the results by induction!

This resource was uploaded by: John