=
+
+ +
+
=
+
+
+
=
+
(
) [ (
) (
)]
(
)(
)
(
)(
k
k k
k
k
k
k
k
k
1
6
2
7 6
3
1 2
13 18
6
1
2
+
+
2 2 9
6
)(
)
k
Hence the result follows for all n Z
∈
+ , by the principle of Mathematical
induction.
¨
Ì Exam ple 0.1.47: Prove by induction
1
1
1
1 i i
n
n
i
n
(
)
+
= +
=
∑
Proof: Assume S n
i i
n
n
i
n
( ):
(
)
1
1
1
1
+
= +
=
∑
.
For n = 1,
S
i i
S
i
( )
(
)
( )
( )
1
1
1
1
1 2
1
1 1
1
1
1
=
+
=
= +
⇒
=
∑
is true.
Assume
S k
i i
k
k
i
k
( ) :
(
)
1
1
1
1
+
= +
=
∑
is true.
Now consider S (k + 1).
1
1
1
1
1
1
2
1
1
1
1
1
i i
i i
k
k
k
k
k
i
k
i
k
(
)
(
) (
) (
)
(
) (
+
=
+
+ +
+
=
+
+
=
=
+
∑
∑
+
+
=
+ +
+
+
=
+
+
1
2
2 1
1
2
1
2
) (
)
[ (
) ]
(
) (
)
k
k k
k
k
k
k
Therefore, S(k) ⇒ S(k + 1). Hence the result follows by Mathematical
Induction.
Ì Exam ple 0.1.48: Prove by induction for n z
∈
+ ,
n
n
n
> ⇒ <
4
2
2
Proof: For n = 5, 2
5 = 32 > 25 = 5
2 .
Introduction
35