Mathematical Foundation of Computer Science

DHARM

DISCRETE THEORY, RELATIONS AND FUNCTIONS 19

Induction Hypothesis

For n greater then 0, assume that

ii k k k

i

k

()/ ( )( )/+=++

=

∑^12126

1

holds for all k ≥ 0 such that k < n.

(Induction Hypothesis with k = n – 1)

ii n nn

i

n

()/( )( )/+=− +

=

−

∑^12116

1

1

Since, ii ii n

i

n

i

n

()/+= +++()/( )/

==

−

∑∑^121212

11

1

Therefore ii n nn nn

i

n

()/( )( )/ ( )/+=− +++

=

∑^1211612
1
= n(n + 1) (n + 2)/6. Proved
Example 1.10. Show that for any n ≥ 4, n! > 2n.
Sol. Let P(n) is n! > 2n. For 0 ≤ n < 4, P(n) is not true. For n = 4, P(4) is 4! < 2^4 (i.e., 24 < 16) so
it is true. Assume that P(k) is true for any k > 4, i.e.,
k! > 2k
or, 2 k! > 2 2k
since, (k + 1) > 2 for any k > 4, hence
(k + 1) k! > 2 k! > 2 * 2k
⇒ (k + 1)! > 2k+1
Therefore, P(k + 1) is true. Hence P(n) is true for any n ≥ 4.
Example 1.11. Show that for every n ≥ 0, xn–1 – 1 is divisible by x – 1.
Sol. Let P(n) is xn – 1 – 1. We begin by checking that P(n) is true for the starting values of n,
i.e., for n = 0, x0 – 1 – 1 = x–1 – 1 = –(x – 1)/x which is divisible by (x – 1). For n = 1, x1–1 – 1 = 0, and
0 is divisible by (x – 1). Assume that P(k) is true for any k ≥ 0, i.e., xk – 1 – 1 is divisible by (x – 1).
Since by division,
(xk^ – 1)/ (x – 1) = xk – 1 + (xk – 1 – 1)/(x – 1)
if (xk – 1 – 1) is divisible by (x – 1), then (xk – 1) is also divisible by (x – 1). Therefore P(+ 1) is true.
Hence P(n) is true for all n ≥ 0.
Example 1.12. Prove that for any n ≥ 1,

in

in

i

n

*()*2122^1

1

=− + +

=

∑

Sol. Let P(n): inin

i

n

*()*2122^1

1

=− + +

=

∑

Here the base case is n = 1. For this case both sides of the equation return value 2. For n

greater than 1, assume that