Sums

Read about sums in the book, chapter 14.1 and 14.2.

Sums of series, e.g. \(1+2+ \dots +n\) or \(2^0 + 2^1 + 2^2 + \dots + 2^n\) can be solved by induction. We we will also see generalizations of these sums.

We talked about the following theorem in the lecture, but did not prove it:

To prove: 1 + x² + ... + xⁿ = (xⁿ⁺¹-1)/(x-1), for x /= 0, x /= 1, n ≥ 0

Proof: By induction over n. Let P(n) = "1 + x² + ... + xⁿ = (xⁿ⁺¹-1)/(x-1)".

Base case: P(0): Then we have 1 = (x-1)/(x-1). OK!

Step case: P(k) => P(k+1), k ≥ 0.

(1.) By the induction hypothesis (I.H.), we know that P(k), in other words 1 + x² + ... + x^k = (x^k+1-1)/(x-1).

(2.) Now we prove P(k+1):

1 + x² + ... + x^k + x^k+1

= (x^k+1-1)/(x-1) + x^k+1 [ by the I.H. ]

= (x^k+1-1)/(x-1) + x^k+1(x-1)/(x-1)

= (x^k+1 - 1 + x^k+1(x-1))/(x-1)

= (x^k+1 - 1 + x^k+2 - x^k+1)/(x-1)

= (x^k+2 - 1)/(x-1)

Which is what we had to prove!