Mathematical Foundation of Computer Science

DHARM

20 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

ik

ik

i

k

*()*2122^1

1

=− + +

=

∑

true for all k ≥ 1 such that k < n.
Induction hypothesis with k = n – 1

in

in

i

n

*()*2222

1

1

=− +

=

−

∑

Since, iiniin
i

n

i

n

***222

1

1

1

=+

=

−

=

∑∑

Thus, in n
i

n

*{()* }*inn

=

∑ =− ++

1

22222

= (n – 2 + n) 2n + 2 = (n – 1) 2n + 1 + 2. Proved.
Example 1.13. Show that for any n ≥ 0,

11 1

1

/(ii )n n/( )

i

n

+= +

=

∑

Sol. Let P(n): 11 1
1

/(ii )n n/( )

i

n

+= +

=

∑

For n = 0, P(0) is true. For n greater than 0, assume that

11 1

1

/(ii )k k/( )

i

k

+= +

=

∑

holds for all k ≥ 0 such that k < n.
For k = n – 1,

11 1

1

1

/(ii ) (n )/n

i

n

+= −

=

−

∑

Since, 11 1 11 1
1

1

1

/(ii ) / (i i ) / (n n )

i

n

i

n

+= ++ +

=

−

=

∑∑

11 11 1

1

/( ) (ii n )/n / (nn )

i

n

+= − + +

=

∑

= (n^2 – 1 + 1) / n (n + 1) = n / (n + 1). Proved.

EXERCISES

1.1 For the set X = {1, 2, 3, ∅}construct the following :

(i)X ∪ P(X) (ii)X ∩ P(X)

(iii)X – ∅ (iv)X – {∅}

(v) Is ∅ ∈ P(X)?

(where P(X) is the power set of X)