Ì Exam ple 0.1.42: Show that any positive integer, n ≥ 2 is either a prime
or a product of primes.
Proof: Basis: n =2 is a prime.
Inductive Hypothesis: For n = k, k is either a prime or a product of primes.
Inductive Step: For n = k + 1, if k + 1 is prime the given statement is true else,
k
pq p q k
+ =
<
1
, ,
⇒ k + 1 is a prod uct of primes.
¨
Ì Exam ple 0.1.43: Prove by Mathematical Induction, for n ≥ 1,
k
n n
n
k
n
2
1
1
2
6
=
∑ =
+
+
(
)(
)
Proof: Let P n
n
n n
n
( )
(
)(
)
= + +
=
+
+
1 2
1 2 1
6
2
2
2
L
Basis: For n = 1, P(1) = 1
2 = 1 (on calculating LHS)
RHS P
=
=
+
+ =
=
( )
(
)(
) ( )( )( )
1
1 1 1 2 1
6
1 2 3
6
1
Therefore P(1) is true.
Inductive Hypothesis:
P K
k
k k
k
( )
(
)(
)
= + +
=
+
+
1 2
1 2 1
6
2
2
2
L
is true.
Inductive Step: We claim that
P K
k
k
k
k
(
)
(
)
(
)(
)(
)
+ = + + + +
=
+
+
+
1 1 2
1
1
2 2 3
6
2
2
2
L
is true.
Now,
1 2
1
1 2
1
1 2 1
1
2
2
2
1
2
2
2
+ + + + +
=
+ + +
+ +
=
+
+
L
L
k
k
k
k
k k
k
(
)
(
) (
)
(
) (
)
6
1
1 2 1 6
1
6
1
2
2
+ +
=
+
+ +
+
=
+
(
)
(
( )
)
(
) (
) (
)
(
)[
k
P k
k k
k
k
k
Q
is true
2
7 6
6
2
k
k
+
+ ]
32
Theory of Automata, Formal Languages and Computation