Inductive Hypothesis: When n = k.
11
12
133
2
2 1
k
k
p
+
+
+
=
Inductive Step: When n = k + 1
11
12
11 11
12
11 133 12
12
3
2 3
2
2 3
2 1
2
k
k
k
k
k
k
p
+
+
•
+
+
+
+
+
=
+
=
−
+
(
)
3
2 1
2
2 1
133 11
12
11 12
133 11 12
=
−
−
=
+
+
+
( )
(
)
(
)
p
p
k
k
Hence it is true for n ≥ 0.
¨
Ì Exam ple 0.1.40: It is known that for any positive integer n ≥ 2,
1
1
1
2
1
2
0
n
n
n
A
+
+ +
+
− >
L
where A is a constant. How large can A be?
Solu tion
Let the value of A be x.
n
x
x
=
+ − >
<






2
1
3
1
4
0
7
12
,
Assume
Inductive Hypothesis:
For n k
k
k
k
x
=
+
+ +
+ +
− >
,
1
1
1
2
1
2
0
L
Induc tive Step:
For n = k+
k
k
k
x
1
1
2
1
3
1
2
1
,
(
)
+
+ +
+ +
+
−
L
=
+
+ +
+ +





 +
+
+
+
− +
−
1
1
1
2
1
2
1
2 1
1
2 2
1
1
k
k
k
k
k
k
x
L
Adding and substracting
1
1
0
k +






=
(1)
But
1
1
1
2
1
2
k
k
k
x p p
+
+ +
+

 

  = +
L
( - positive)
30
Theory of Automata, Formal Languages and Computation