M2 Mathematical Induction

17ai) S1 = 1, S2 = 1 + 2 + 1 = 4, S3 = 1 + 2 + 3 + 2 + 1 = 9

b) Let P(n) be the statement Sn = n2, then P(1) is true according to (i).

Suppose that P(k) is true for some positive integer k, i.e.

1 + 2 + 3 + ... + k + (k - 1) + ... + 2 + 1 = k2

Now for P(k + 1), LHS is:

1 + 2 + 3 + ... + k + (k + 1) + k + (k - 1) + ... + 2 + 1

= k2 + (k + 1) + k

= k2 + 2k + 1

= (k + 1)2

Hence P(k + 1) is also true and P(n) is true for all positive integers n.

18a) 1 + 1/2 + ... + 1/2n-1

Let x = 1/2, then

1 + x + ... + xn-1 = (xn - 1)/(x - 1)

= (1/2n - 1)/(1/2 - 1)

= 2(1 - 1/2n)

So Sn = 2 - 2(1 - 1/2n) = 1/2n-1

b) Let P(n) be the statement Sn = 1/2n-1

When n = 1, S1 = 1, 1/2n-1 = 1

Hence P(1) is true.

Suppose that P(k) is true for some positive integer k, i.e.

Sk = 2 - (1 + 1/2 + ... + 1/2k-1) = 1/2k-1

Subtracting 1/2k on both sides:

2 - (1 + 1/2 + ... + 1/2k-1) = 1/2k-1 - 1/2k

= (1/2k)(2 - 1)

= 1/2k

Hence P(k + 1) is also true and P(n) is true for all positive integers n.

2012-04-17 08:58:19 補充：
Consider
(x - 1)(1 + x + ... + xn-1) = (x - 1) + (x2 - x) + (x3 - x2) + ... + (xn - xn-1)

= xn - 1

Hence

(1 + x + ... + xn-1) = (xn - 1)/(x - 1)

bcoz im not clever enough, pls. could ching shows 1or2 more steps?
1 + x + ... + xn-1
=steps
=steps
= (x^n - 1)/(x^ - 1)
= (1/2^n - 1)/(1/2^ - 1)