https://docs.google.com/document/d/1fznnCq_PLW8fjUCbguzODDwwiTamZe0R/edit?usp=sharing&ouid=109474854956598892099&rtpof=true&sd=true
Mathematical Induction
Principle of Mathematical Induction and its simple applications
FIRST PRINCIPLE OF MATHEMATICAL INDUCTION
The proposition P(n) involving a natural number n is assumed to be true for all n ∈ N, follows the following three steps:
Step -I (Verification step)
Actual verification of the proposition P(n) for the starting value of n = i.
Step -II (Induction step)
Assuming that if P(n) is true for n = k; k ≥ i, prove that it is also true for
n = k + 1.
Step -III (Generalization step)
Combining the above two steps leads to the conclusion that P(n) is true for all integers n ∈ N.
SECOND PRINCIPLE OF MATHEMATICAL INDUCTION (EXTENDED PRINCIPLE)
Sometimes, the first principle of mathematical induction does not suffice. In such cases we use the extended principle as below:
Step -I (Verification step)
We verify that P(n) is true for i and (i + 1) both.
Step -II (Induction step)
Assume that P(n) is true for n = k and n = k + 1, k ≥ i, and prove that P(n) is true for n = (k + 2).
Step -III (Generalization step)
Combining the above two steps leads to the conclusion that P(n) is thus true
n ∈ N.
C H A P T E R
CHAPTER INCLUDES :
First principle of Mathematical Induction
Second (extended) Principal of
Mathematical Induction
Application of Mathematical Induction
Solved Examples
APPLICATION OF MATHEMATICAL INDUCTION
Identities Type Problems
n5 + n3 + 7n
Show by using induction that 5
3 15
is a natural number for n ∈ N.
Solution :
n5 + n3 + 7n
Let P (n) : 5
3 15
is a natural number
n5 + n3 + 7n = 15 + 13 + 7
= 1 + 1 + 7 =
When n = 1, 5
3 15 5
3 15
5 3 15
1, which is a natural number
Hence P (1) is true …(A)
Let P (m) be true
m5 + m3 + 7m
⇒ 5 3
15 is a natural number …(i)
To prove P (m + 1) is true i.e.,
(m + 1)5 + (m + 1)3 +
5 3
Expanding (ii), we get
1 (m5 + 5m4 + 10m3 + 10m2 + 5m + 1) + 1 (m3 + 3m2 + 3m + 1) + 7
(m + 1)
5
= m5 + m3 + 7m +
(m 4 +
2m3 +
3m2 +
3
2m)
15
+ 1 + 1 + 7
5 3 15 5 3 15
= m5 + m3 + 7m +
(m4 + 2m3 + 3m2 + 2m) + 1
5 3 15
⎡ Θ m5 + m3 + 7m ⎤
= a natural number ⎢
5 3 15
is a natural number from (i) ⎥
⎥⎦
Hence P (m + 1) is true whenever P (m) is true …(B) From (A) and (B), it follows that P (n) is true for all natural numbers n.
Divisibility Type Problems
To prove that P(n) is divisible by x, following procedure is followed
First we show that P(1) is divisible by x.
Assuming that P(m) is divisible by x, it is proved that P(m + 1) is also divisible by x. For this either divide
P(m + 1) with P(m) and show that remainder is divisible by x. or
Split P(m + 1) = P(m) . I + R; I ∈ Z and show that R is divisible by x.
Show that n3 + (n + 1)3 + (n + 2)3 is divisible by 9 for every natural number n.
Solution :
Let f (n) = n3 + (n + 1)3 + (n + 2)3
Let P (n) : f (n) i.e., n3 + (n + 1)3 + (n + 2)3 is divisible by 9. Now f (1) = 13 + 23 + 33 = 36, which is divisible by 9.
∴ P (1) is true. …(A)
Let P (m) be true ⇒ f (m) = m3 + (m + 1)3 + (m + 2)3 is divisible by 9.
⇒ f (m) = m3 + (m + 1)3 + (m + 2)3 = 9k, where k is an integer …(i) To prove P (m + 1) is true i.e., f (m + 1) is divisible by 9.
Now, f (m + 1) = (m + 1)3 + (m + 2)3 + (m + 3)3
= (m + 1)3 + (m + 2)3 + m3 + 9m2 + 27m + 27
= [m3 + (m + 1)3 + (m + 2)3] + 9m2 + 27m + 27
= 9k + 9 (m2 + 3m + 3),
which is divisible by 9.
Hence P (m + 1) is true whenever P (m) is true. …(B) From (A) and (B), it follows that P (n) is true for all natural numbers n.
Inequalities Type Problems
If a and b are positive, use mathematical induction to prove that
⎛ a + b ⎞n
an + bn
⎜ ⎟ ≤
⎝ 2 ⎠
Solution :
2 ∀ n ∈ N .
⎛ a + b ⎞n an + bn
P (n) : ⎜ ⎟ ≤
⎝ 2 ⎠ 2
Step I. For n = 1
P(i ) : a + b ≤ a + b
2 2
which is true for n = 1,
Step II. Assume it is true for n = k, then
⎛ a + b ⎞k ak + bk
P(k ) : ⎜ ⎟ ≤
⎝ 2 ⎠ 2
Step III. For n = k + 1,
⎛ a + b ⎞k+1
⎛ a + b ⎞ ⎛ a + b ⎞k
⎛ a + b ⎞ ⎛ ak + bk ⎞
⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ≤ ⎜
⎟ ⎜ ⎟
(By assumption step)
⎝ 2 ⎠ ⎝ 2 ⎠ ⎝ 2 ⎠
⎝ 2 ⎝ ⎟
⎛ a + b ⎞k +1 1
⇒ ⎜ ⎟
⎝ ⎠
≤ [(ak+1 + bk+1) + ak b + abk ] 4
⎛ a + b ⎞k+1 1
⇒ ⎜ ⎟
⎝ ⎠
≤ [2 (ak +1 + bk+1) – ak +1 – bk+1 + ak b + abk ] 4
⎛ a + b ⎞k +1 1
⇒ ⎜ ⎟
⎝ ⎠
≤ [2 (ak +1 + bk +1) – (a − b) (ak − bk )] 4
⎛ k +1 k +1 ⎞
≤ ⎜ ⎟ −
(a − b) (ak − bk )
⎜ ⎟
⎝ ⎠
⎛ a + b ⎞k +1
ak +1 + bk +1
∴ ⎜ ⎟ ≤
⎝ ⎠ 2
Hence the statement is true for n = k + 1 and by the principle of induction it is true for all n ∈ N.
Problems Based on Extended Principle of Mathematical Induction
If the given problem cannot be solved by direct use of principle mathematical induction, try to use the extended principle of mathematical induction.
If a1 = 1, a2 = 5 and an+2 = 5an+1 – 6an, n ≥ 1. Show by using mathematical induction that an = 3n – 2n.
Solution :
Let P (n) : an = 3n – 2n
When n = 1, L.H.S. = a1 = 1 (given) and R.H.S. = 31 – 21 = 3 – 2 = 1.
∴ L.H.S. = R.H.S.
When n = 2, L.H.S. = a2 = 5 (given) and R.H.S. = 32 – 22 = 5
Thus L.H.S = R.H.S.
Hence P (1) and P (2) are true …(A)
Let P (m) and P (m + 1) be true
⎧⎪am = 3m − 2m
⇒ ⎨
⎩am+1
m +1
− 2m +1
…(ii)
To prove P (m + 2) is true i.e., am+2 = 3m+2 – 2m+2 Given, an+2 = 5an+1 – 6an
∴ am+2 = 5am+1 – 6am
= 5 (3m+1 – 2m+1) – 6 (3m – 2m)
= (5.3m+1 – 6.3m) – (5.2m+1 – 6.2m)
= 3m (15 – 6) – 2m (10 – 6)
= 3m.9 – 2m.4
= 3m+2 – 2m+2.
Hence P (m + 2) is true whenever P (m) and P (m + 1) are true. …(B)
From (A) and (B), by the principle of mathematical induction it follows that P (n) is true for all natural numbers n.
SOLVED EXAMPLES
Example 1 :
Use the principle of mathematical induction to prove that for all n ∈ N.
= 2cos ⎛ π ⎞
⎜ 2n +1 ⎟
⎝ ⎠
when the L.H.S. contains n radical signs.
Solution :
= 2cos ⎛ π ⎞
Let P (n) =
⎜ 2n +1 ⎟
…(i)
Step I. For n = 1,
L.H.S. of (i) =
and R.H.S. of (i)
⎝ ⎠
= 2 cos ⎛ π ⎞
2
⎝ ⎠
= 2 cos ⎛ π ⎞
⎜ ⎟
⎝ 4 ⎠
Therefore, P (1) is true.
Step II. Assume it is true for n = k,
P (k ) =
= 2cos ⎛ π ⎞
⎜ 2k +1 ⎟
(k radical sign) ⎝ ⎠
Step III. For n = k + 1
P (k + 1) =
(k + 1) radical sign
=
= (By assumption step)
=
=
=
= 2 cos ⎛ π ⎞
⎜ 2k +2 ⎟
⎝ ⎠
This shows that the result is true for n = k + 1. Hence by the principle of mathematical induction, the result is true for all n ∈ N.
Prove that 1 +
+ +… +
≥ , n ∈ N.
Solution :
For n = 1, L.H.S. = 1,
R.H.S. = 1 so L.H.S. = R.H.S. …(i) Assume the result for n = k,
i.e., 1+
+ +… + 1 ≥
…(ii)
For n = k + 1,
L.H.S. = 1+
+ …+ 1 +
≥ + [Using (ii)]
+ [Note]
= + − =
i.e., the result is true for n = k + 1
Hence by induction, the result is true n ∈ N.
❑ ❑ ❑
PHYSICS-15-10- 11th (PQRS) SOLUTION
XI (PQRS) PHYSICS REVIEW TEST-5 Select the correct alternative. (Only one is correct) [15 × 3 = 45] There is NEGATIVE marking. 1 mark will be deducted for each wrong answer. Q.31 Two trains, which are moving along different tracks in opposite directions towards each other, are put on the same track due to a mistake. Their drivers, on noticing the mistake, start slowing down the trains when the trains are 300 m apart. Graphs given below show their velocities as function of time as the trains slow down. The separation between the trains when both have stopped, is: (A) 120 m (B) 280 m (C) 60 m (D*) 20 m 1 [Sol: x1 = 2 1 × 10 × 40 = 200 m; x2 = – 2 × 8 × 20 = –80 m xreletive = x1 + x2 = 280 separation = 300 – 280 = 20 m (D) ] Q.32 One end of a thin uniform rod of length L and mass M is riveted to the centre of a uniform circular disc of radius r and mass 2 M so that the rod is normal to the disc. The centre of mass of the combination from the centre of the disc is at dist
Comments
Post a Comment