Transcript File - Siby Sebastian

MATHEMATICAL
INDUCTION
SYNOPSIS
 Introduction
 Types
of mathematical statements
 Induction Method
 Deduction method
 Principle of mathematical induction
 Problems
INTRODUCTION
 The
key basis for mathematical
thinking is deductive and inductive
reasoning.
 There are mainly three methods to
prove a mathematical statement.
They are:
 Inductive Method
 Deductive method
 Contradiction method
DEDUCTION METHOD
It is an application of general case to a
particular case.
Example:
A number which is divisible by 9 is
divisible by 3.
918 is divisible by 9 implies 9+1+8=18
and hence a multiple of 3.
Induction Method
Method of proving a statement from
particular to general is called Induction.
 Example:
 2 is divisible by 2
 4 is divisible by 2
 6 is divisible by 2.



Every even number is divisible by 2.
ILLUSTRATION
 To
understand the basic principle of
mathematical induction, the best
example is that of thin rectangular
tiles placed as shown in the next
slide:
 When
the first tile is pushed, all the
tiles will fall. To be absolutely sure
that the tiles will fall, it is optimum
to know that the first tile falls and
the event that any tile falls, its
successor necessarily falls.
This is the major principle of
mathematical induction.
Principle of mathematical induction
Let P(n) be a mathematical statement
involving the natural number n such
that
 (i) P(1) is true and
 (ii) P(k) is true
P(k+1) is true.




P(n) is true for all natural numbers.
THE PRINCIPLE
 THERE
ARE 3 MAJOR STEPS IN
SOLVING PROBLEMS ON
INDUCTION:
1. Proving that the given statement
P(n) is true for n=1.
2. Supposing that P(n) is true for
n=k.
3. then proving that the statement is
true for n=k+1.
Examples
(i) Prove that 1+3+5+…+(2n-1)=n2
 Solution:
 Let P(n) be the given statement.
 Put n=1. LHS=1=RHS. Hence P(1) is true.
 Let P(k) be true.That is, 1+3+…+(2k1)=k2
 To Prove:P(k+1) is true.
 Now,1+3+…+(2k-1)+(2k+1)=k2+(2k+1)

=(k+1)2
Hence it is true for all n.

Example








(ii) Prove by principle of mathematical
induction that 25n>33n for all n N
Solution:
Let P(n):25n>33n
Here P(1):25>33 or 32>27, which is true.
Let P(m) be true. That is,25m>33m
Now, in P(m+1),LHS=2 5(m+1 )
=25m . 25
=32 . 25m ------(1)
RHS=33(m+1)

=33m . 33

=27 .33m ----------(2)
 As 32>27,LHS>RHS and hence P(m+1) is
true.
 Hence P(n) is true for all values of n  N

Example
(iii) Prove by principle of mathematical
induction that n(n+1)(2n+1) is divisible
by 6 for all natural numbers n.
 Solution:
 Let a=n(n+1)(2n+1)
 now for n=1, a= 1(1+1)(2+1)

=1X2X3=6, which is
divisible by 6.
 Hence P(1) is true.










Let us suppose that P(m) is true.
Hence m(m+1)(2m+1) is divisible by 6.
Let m(m+1)(2m+1) =6k
Consider a for n=m+1
a= (m+1)(m+2)(2m+3)
= (m+1)(m+2)((2m+1)+2)
=(m+1)m(2m+1)+(m+1).2(2m+1)+2(m+1)(m+2)
= m(m+1)(2m+1)+2(m+1)(3m+3)
= m(m+1)(2m+1)+6(m+1)2
6k+6(m+1)2
 6(k+(m+1)2), which is divisible by 6.
 Hence P(m+1) is true when P(m) is
true.
 Hence n(n+1)(2n+1) is divisible by 6 n N

QUESTIONS FOR PRACTICE


Using principle of mathematical induction, prove that
(1) 1+2+3+…+n= n( n  1) , n  N .
2
n( 2n  1)( 2n  1)
, n  N
3

(2) 12+32+52+…+(2n-1)2 =

3
n
(3) 12+22+32+…+n2>
, n  N
3

(4) Prove that 2n>n for all n




(5)
(6)
(7)
(8)
N
For each natural number n, 32n-1 is divisible by 8.
For each natural number n, 152n-1+1 is divisible by 16.
Prove that n(n+1) is an even integer for all natural number n.
Prove that (a b)n=anbn, for all natural number n.