Counting clockwise from n 1 , label the other numbers n n
n
2
3
36
, ,
,
KK
.
For the result to be false, we should have
n n n
n n n
n
n
n
n
n
1
2
3
2
3
4
34
35
36
35
55
55
55
+ + <
+ + <
+
+
<
+
,
,
,
LLL
LLL
36
1
36
1
2
55
55
+ <
+ + <
n
n
n n
,
.
In all the inequalities above, the terms n 1 , n 2 , n 3 , ...... appear exactly three
times.
Therefore adding the 36 inequalities we get
3
3
36 35 1980
1
36
1
36
n
j
j
j
j
=
=
∑
∑
=
<
=
( )
.
But
j
j =
∑ =
=
1
36
36 37 666
( )( )
.
But this gives the contradiction that
1998 = 3 (666) < 1980.
Ì Exam ple 0.1.46: Prove by induction,
1.3
3.5
+
+
+
+ =
+
+
2 4
2
1 2 1
6
.
(
)
(
)(
)
L n n
n n
n
Proof:
Basis:
1.3 =
=
( )( )( )
1 2 9
6
3
This result is true for n = 1.
Inductive Hypothesis: Assume that the result is true for n k
= ≥
( )
1 .
i.e.,
1.3 +
+ +
+ =
+
+
2 4 35
2
1 2
7
6
.
.
(
)
(
)(
)
L k k
k k
k
Inductive Step: For n = k + 1,
[
.
(
)] (
)(
)
(
)(
)
(
1.3 +
+
+ + +
+
=
+
+





 +
2 4
2
1
3
1 2
7
6
L k k
k
k
k k
k
k
k
+
+
1
3
)(
)
34
Theory of Automata, Formal Languages and Computation