State Principle of Mathematical Induction, Solution and Principle of Mathematical Induction Proof
A proof by induction consists of –
1) The base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases.
2) The second case, the inductive step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1.
These establish that the statement holds for every natural number n.
Let’s consider a statement P(n), where n is a natural number. Then to determine the validity of P(n) for every n, we can use the following principle:
Step 1: Check whether the given statement is true for n = 1.[Base Case]
Step 2: Assume that the given statement P(n) is also true for n = k, where k is any positive integer. [Inductive hypothesis]
Step 3: Prove that the result is true for P(k+1) for any positive integer k.[Induction step]
If the above-mentioned conditions are satisfied, then it can be concluded that P(n) is true for all n natural numbers. Thus, this is the mathematical induction formula approach.
Properties of Mathematical Induction
Property a) mentioned above is simply a statement of a fact. In these situations, where the statement is true for all the cases (assuming n≥5), then the step a) shall start from n=5 and we shall hence verify the result for n=5, i.e., P(5).
Property b) shows a conditional property (conditional property is the occurrence of an event B in relationship to an event A given that event A has already occurred.) as it does not confirm that the given statement is true for n=k, but if it is true for n=k then it should also be true for n=k+1.
Theorem
For any n ∈ N,
[sum_{i=1}^{n} i = frac{n(n+1)}{2}]
Proof
Base case n = 1 : If n = 1, the left side is 1 and the right side is [frac{1(2)}{2} = 1].
So, the theorem holds when n = 1.
Inductive hypothesis : Suppose the theorem holds for all values of n upto some k, k ≥ 1.
Inductive step : Let n = k + 1. Then our left side is
[sum_{i=1}^{k+1} i = (k+1) + sum_{i=1}^{k} i]
= [(k+1) + frac{k(k+1)}{2}], by our inductive hypothesis
= [frac{2(k+1)}{2} + frac{k(k+1)}{2}]
= [frac{2(k+1) + k(k+1)}{2}]
= [frac{(k+1)(k+2)}{2}]
which is our right side. So, the theorem holds for n = k + 1. By the principle of mathematical induction, the theorem holds for all n ∈ N.
Principle of Mathematical Induction Examples
Here are two mathematical induction problems inter 1st year.
Prove the Following using Principle of Mathematical induction
-
Prove that for any positive integer number n, n 3 + 2n will be divisible by 3
-
Prove that: 13 + 23 + 33 + … + n 3 = n 2 (n + 1) 2 / 4 for all positive integers n.
Solution to Problem 1:
Let Statement P (n) be defined in the form n 3 + 2n is divisible by 3
Step 1: Basic Step
We first show that p (1) is true. Let n = 1 and formulate n 3 + 2n
1 3 + 2(1) = 3
3 is divisible by 3 hence p (1) is true.
Step 2: Inductive Hypothesis
We now assume that p (k) is true
k 3 + 2k will be divisible by 3 and will be equivalent to
k 3 + 2 k = 3 B , where B is a positive integer.
Step 3: Inductive Steps
We now consider the algebraic expression (k + 1) 3 + 2 (k + 1); expand it and group like terms
(k + 1) 3 + 2(k + 1) = k 3 + 3 k 2 + 5 k + 3
= [ k 3 + 2 k] + [3 k 2 + 3 k + 3]
= 3 B+ 3 [ k 2 + k + 1 ] = 3 [ B + k 2 + k + 1 ]
Therefore, (k + 1) 3 + 2 (k + 1) will also be divisible by 3 and hence, statement P(k + 1) is true.
Solution to Problem 2:
Statement P (n) is defined by
1 3 + 2 3 + 3 3 + … + n 3 = n 2 (n + 1) 2 / 4
Step 1: Basic Step
We first show that p (1) is true.
Left Side = 1 3 = 1
Right Side = 1 2 (1 + 1) 2 / 4 = 1 hence p (1) is true.
Step 2: Inductive Hypothesis
We now assume that p (k) is true
1 3 + 2 3 + 3 3 + … + k 3 = k 2 (k + 1) 2 / 4
Step 3: Inductive Steps
add (k + 1) 3 to both sides
1 3 + 2 3 + 3 3 + … + k 3 + (k + 1) 3 = k 2 (k + 1) 2 / 4 + (k + 1) 3
factor (k + 1) 2 on the right side
= (k + 1) 2 [ k 2 / 4 + (k + 1) ] set to common denominator and group
= (k + 1) 2 [ k 2 + 4 k + 4 ] / 4
= (k + 1) 2 [ (k + 2) 2 ] / 4
We started from statement P(k) and can show:
1 3 + 2 3 + 3 3 + … + k 3 + (k + 1) 3 = (k + 1) 2 [ (k + 2) 2 ] / 4
Which is the statement P(k + 1).