Assume the result for n k
= ≥
( ) :
5
2
k > k
2 .
For k > 3, we have
k k
k
k
k
k
k
k
k
k
k
k
k
k
(
)
(
− >
⇒
> +
⇒
>
⇒
+
>
+
⇒
>
+
>
+
2 1
2 1
2
2
2
2
2
2
2
2
2
1
2
2
2 k
k
k
+
⇒
> +
+
1
2
1
1
2
)
(
)
Hence the result is true for n ≥ 5 by the principle of Mathematical Induction.
¨
Ì Exam ple 0.1.49: Given S (n) as the statement
i
n
i
n
=
∑ =
+












1
2
1
2
2
.
Prove that the truth of S(k) implies the truth of S(k + 1) by Mathematical
induction.
Proof: Assume S(k). For S(k + 1), we have
i
k
k
k
k
i
k
=
+
∑ = +



















 + +
=
+ +

1
1
2
2
1
2
2
1
1
4
(
)




 + +






=
+
+ + +












=
+
2 2 2
1
1
1
4
2
2
k
k
k
k
(
)
(
)
( 1
1
2
2
2
) +














Therefore S k
s k
( )
(
)
⇒
+ 1 .
¨
Ì Exam ple 0.1.50: Show that if we select 151 distinct computer
engineering courses numbered between 1 and 300 inclusive, at least two
are consecutively numbered (using Pigeonhole Principle).
36
Theory of Automata, Formal Languages and Computation