3.1: Proof by Induction
( \newcommand{\kernel}{\mathrm{null}\,}\)
Inductive reasoning is the process of drawing conclusions after examining particular observations. This reasoning is very useful when studying number patterns. In many situations, inductive reasoning strongly suggests that the statement is valid, however, we have no way to present whether the statement is true or false, for example, Goldbach conjecture. But, in this class, we will deal with problems that are more accessible and we can often apply mathematical induction to prove our guess based on particular observations. For example, when we predict a nth term for a given sequence of numbers, mathematics induction is useful to prove the statement, as it involves positive integers.
Process of Proof by Induction
There are two types of induction: regular and strong. The steps start the same but vary at the end. Here are the steps. In mathematics, we start with a statement of our assumptions and intent:
Let p(n),∀n≥n0,n,n0∈Z+ be a statement. We would show that p(n) is true for all possible values of n.
- Show that p(n) is true for the smallest possible value of n: In our case p(n0). AND
- For Regular Induction: Assume that the statement is true for n=k, for some integer k≥n0. Show that the statement is true for n = k + 1.
OR
For Strong Induction: Assume that the statement p(r) is true for all integers r, where n0≤r≤k for some k≥n0. Show that p(k+1) is true.
If these steps are completed and the statement holds, we are saying that, by mathematical induction, we can conclude that the statement is true for all values of n≥n0.
We shall use the following template for proof by induction:
Template for proof by induction
In order to prove a mathematical statement involving integers, we may use the following template:
Suppose p(n),∀n≥n0,n,n0∈Z+ be a statement.
For regular Induction:
- Base Case: We need to show that p(n) is true for the smallest possible value of n: In our case show that p(n0) is true.
- Induction Hypothesis: Assume that the statement p(n) is true for any positive integer n=k, for s k≥n0.
- Inductive Step: Show that the statement p(n) is true for n=k+1..
For strong Induction:
- Base Case: Show that p(n) is true for the smallest possible value of n: In our case p(n0).
- Induction Hypothesis: Assume that the statement p(n) is true for all integers r, where n0≤r≤k for some k≥n0.
- Inductive Step: Show that the statement p(n) is true for n=k+1..
If these steps are completed and the statement holds, by mathematical induction, we can conclude that the statement is true for all values of n≥n0.
Example 3.1.1
Solution
Let . Then
is true since clearly
. Thus the statement is true for
.
Assume that is true for some
.
Example 3.1.2
Prove that 1+2+...+n=n(n+1)2,∀n∈Z.
Solution:
Base step: Choose n=1. Then L.H.S =1. and R.H.S =(1)(1+1)2=1
Induction Assumption: Assume that 1+2+...+k=k(k+1)2, for k∈Z.
We shall show that 1+2+...+k+(k+1)=(k+1)[(k+1)+1]2=(k+1)(k+2)2
Consider 1+2+...+k+(k+1)
=k(k+1)2+(k+1)
=(k+1)(k2+11)
=(k+1)(k+22)
=(k+1)(k+2)2.
Thus, by induction we have 1+2+...+n=n(n+1)2,∀n∈Z.
We will explore examples that are related to number patterns in the next section.