Induction
Mathematical Induction
Subjects to be Learned
- first principle of mathematical induction
- basis step
- induction hypothesis
- induction
- second principle of mathematical induction
Contents
First Priciple of Mathematical Induction
As we have seen in recursion ,
the set of natural numbers can be defined recursively,
and its elements can be generated one by one starting with 0 by adding 1.
Thus the set of natural numbers can be described completely by specifying the basis
element (0), and the process of generating an element from a known element in the set.
Taking advantage of this, natural numbers can be proven to have certain properties
as follows:
First it is proven
that the basis element,
that is 0, has the property in question (basis step).
Then it is proven that if an arbitrary natural
number, denote it by n, has the property in question, then the next element, that is
n + 1, has that property (inductive step).
When these two are proven, then it follows that all the natural
numbers have that property. For since 0 has the property by the basis step, the element next to it, which is
1, has the same property by the inductive step. Then since 1 has the property, the element next to it,
which is
2, has the same property again by the inductive step. Proceeding likewise, any natural number can be shown to have
the property. This process is somewhat analogous to the knocking over a row of dominos with knocking over the first domino
corresponding to
the basis step.
More generally mathematical statements involving a natural number n such as
1 + 2 + ... + n = n( n + 1 )/2
can be proven by mathematical induction by the same token.
To prove that a statement P(n) is true for all natural number , where
is a natural number,
we proceed
as follows:
Basis Step: Prove that P( ) is true.
Induction: Prove that for any integer , if P(k) is true
(called induction hypothesis), then
P(k+1) is true.
The first principle of mathematical induction states that if the basis step
and the inductive step are proven, then P(n) is true for all natural number
.
As a first step for proof by induction, it is often a good idea to restate
P(k+1) in terms of P(k)
so that P(k), which is assumed to be true, can be used.
Example:
Prove that for any natural number n, 0 + 1 + ... + n = n( n + 1 )/2 .
Proof:
Basis Step:
If n = 0,
then LHS = 0, and RHS = 0 * (0 + 1) = 0 .
Hence LHS = RHS.
Induction: Assume that for an arbitrary natural number n,
0 + 1 + ... + n
= n( n + 1 )/2 . --------
Induction Hypothesis
To prove this for n+1, first try to express LHS for
n+1 in terms of LHS
for n, and somehow use the induction hypothesis.
Here let us try
LHS for n + 1 =
0 + 1 + ... + n + (n + 1) =
(0 + 1 + ... + n) + (n + 1) .
Using the induction hypothesis, the last expression can be rewritten as
n( n + 1 )/2 + (n + 1) .
Factoring (n + 1) out, we get
(n + 1)(n + 2) / 2 ,
which is equal to the RHS for n+1.
Thus LHS = RHS for n+1.
End of Proof.
More examples can be found
here.
Also an
example
is given on how induction might be used to derive a new result.
Test Your Understanding of Induction
Indicate which of the following statements are correct and which are not.
Click True or False , then Submit. There is one set of questions.
Second Priciple of Mathematical Induction
There is another form of induction over the natural numbers based on the
second principle of induction to prove assertions of the form
x P(x) .
This form of induction does not require the basis step, and in the inductive step
P(n) is proved assuming
P(k) holds for all k
< n .
Certain problems can be proven more easily by using the second principle than the first principle
because P(k) for all k < n can be used rather than
just P(n - 1) to prove P(n).
Formally the second principle of induction states that
if
n [
k [ k < n
P(k) ]
P(n) ] ,
then
n P(n)
can be concluded.
Here
k [ k < n
P(k) ]
is the induction hypothesis.
The reason that this principle holds is going to be explained
later after a few examples of proof.
Example 1: Let us prove the following equality using the second principle:
For any natural number n ,
1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2.
Proof: Assume that
1 + 3 + ... + ( 2k + 1 ) = ( k + 1 )2
holds for all
k,
k
< n.
Then 1 + 3 + ... + ( 2n + 1 ) = ( 1 + 3 + ... + ( 2n - 1 ) ) + ( 2n + 1 )
= n2 + ( 2n + 1 ) = ( n + 1 )2 by the induction hypothesis.
Hence by the second principle of induction
1 + 3 + ... + ( 2n + 1 ) = ( n + 1 )2
holds for all natural numbers.
Example 2: Prove that for all positive integer n,
i ( i! )
= ( n + 1 )! - 1
Proof: Assume that
1 * 1! + 2 * 2! + ... + k * k! = ( k + 1 )! - 1
for all k,
k
< n.
Then
1 * 1! + 2 * 2! + ... + ( n - 1 ) * ( n - 1 )! + n * n!
= n! - 1 + n * n! by the induction hypothesis.
= ( n + 1 )n! - 1
Hence by the second principle of induction
i ( i! )
= ( n + 1 )! - 1
holds for all positive integers.
Example 3: Prove that any positive integer n > 1,
can be written as the product of prime numbers.
Proof: Assume that for all positive integers k,
n > k > 1,
k can be written as the product of prime numbers.
We are going to prove that n can be written as the product of prime numbers.
Since n is an integer, it is either a prime number or not a prime number.
If n is a prime number, then it is the product of 1, which is
a prime number, and itself. Therefore the statement holds true.
If n is not a prime number, then it is a product of two positive integers,
say p and q. Since both p and q
are smaller than n, by the induction hypothesis they can be written
as the product of prime numbers (Note that this is not possible if the First Principle
is being used).
Hence n can also be written as the product of prime numbers.
Test your understanding of second principle of induction :
Indicate which of the following statements are correct and which are not.
Click True or False , then Submit. There is one set of questions.
Next -- Relation
Back to Study Schedule
Back to Table of Contents