=
+
+
+
(
) (
) (
)
k
k
k
1
2 2 3
6
⇒ P(k+1) is true.
Thus we have, if P(k) is true, P(k+1) is also true. By principle of Mathematical
Induction, we have
k
n n
n
n
k
n
2
1
1 2 1
6
1
=
+
+
≥
=
∑
(
)(
) ,
¨
Ì Exam ple 0.1.44: Prove that 2
n
n
> , for all n N
∈ , by using Mathematical
Induction.
Proof: Let P n
n
n
( )
.
=
− >
2
0
Basis: For n = 1, P(1) = 2
1 – 1 = 2 – 1 = 1 > 0.
Therefore P(1) is true.
Inductive Hypothesis: Let us assume that P(k) is true. Here we have k as a
positive integer.
⇒
−
2
k
k is pos i tive inte ger
⇒
− =
2
k
k m
(1)
Inductive Step: To prove that P(k + 1) is also positive. Let us consider
2
1
1
k
k
+
− +
(
).
We have
2
1 2 2
1
2
1
2
1
1
k
k
k
k
k m k
k
m
+
− + =
− −
=
+
− −
= +
−
=
(
)
( )
(
)
positive (Q is positive)
m
⇒ If P(k) is true, P(k + 1) is also true.
Hence by Mathematical Induction, P(n) is true, i.e.,
2
0 2
n
n
n
n n N
− > ⇒ > ∀ ∈
,
¨
Ì Exam ple 0.1.45: A wheel of fortune has the numbers from 1 to 36
painted on it in at random. Prove that irrespective of how the numbers are
situated, three consecutive numbers total 55 or more.
Solu tion
Let n 1 be any number on the wheel.
Introduction
33