Lecture Overview L11−P. 1 Series and Summations Examples:

Annuities

Book Stacking Evaluating Sums L11−P. 2

Important for algorithms and systems We would like to have closed form At least approximate its value well enough Annuities L11−P. 3

Would you prefer a million dollars today or $50,000 a year for the rest of your life?

An n-year, m-payment annuity pays m dollars at the start of each year for n years.

We estimate the fixed annual interest rate p around 8%

Ten dollars will be (1 + p) = $10.80 in a year, (1 + p)^{2} ≈ $11.66 in two years, and so forth.

Looked at another way, ten dollars paid out a year from now are only really worth 1/(1+p) ≈ $9.26 today.

The reason is that if we had the $9.26 today, we could invest it and would have $10.00 in a year anyway.

Therefore, p determines the value of money paid out in the future.

The Value of an Annuity L11−P. 4

First payment of m dollars is truly worth m dollars. Second payment a year later is worth only m/(1 + p), Third payment is worth m/(1 + p)^{2}, n-th payment is only m/(1 + p)^{n−1}, The total value V is:

V = ∑_{i=1}^{n} \frac{m}{(1+p)^{i−1}} “Closed form” mathematical expression without any summation or product.

Summation of a geometric series is:

Theorem: For all n ≥ 1 and all x ≠ 0, ∑_{i=0}^{n−1} x^{i} = \frac{1−x^{n}}{1−x}.

We have:

V = ∑_{i=1}^{n} \frac{m}{(1 + p)^{i−1}}

= ∑_{j=0}^{n−1} \frac{m}{(1 + p)^{j}} (substitute j = i − 1)

= m ∑_{j=0}^{n−1} x^{j} (substitute x = \frac{1}{1 + p})

Thus we have \frac{m−mx^{n}}{1−x} where x is \frac{1}{1+p}.

So for m =$50,000, n =20, and p = 0.8 we have V ≈ $530, 180. Better have $550,000 now!

The Sum of a Geometric Series L11−P. 6

So we need to prove the Theorem: ∀n ≥ 1 and all ∀x ≠ 0, ∑_{i=0}^{n−1} x^{i} = \frac{1−x^{n}}{1−x}.

We prove by induction on n. P (n) ∀x ≠ 1 ∑_{i=0}^{n−1} x^{i} = \frac{1−x^{n}}{1−x}.

Base: P (1) holds, since ∑_{i=0}^{0} x^{i} = x^{0} = 1 and \frac{1−x^{1}}{1−x} = 1.

Step: Assume ∀x ≠ 1, ∑_{i=0}^{n−1} x^{i} = \frac{1−x^{n}}{1−x}, and prove

∀x ≠ 1, ∑_{i=0}^{n} x^{i} = \frac{1−x^{n+1}}{1−x}.

∑_{i=0}^{n} x^{i} = x^{n} + ∑_{i=0}^{n−1} x^{i}
= x^{n} + \frac{1 − x^{n}}{1 − x}
= \frac{x^{n}(1 − x) + 1 − x^{n}}{1 − x}
= \frac{1 − x^{n+1}}{1 − x}

How the formula was found??

The trick is to let S be the value of the sum:

S = 1 + x + x^{2} + … + x^{n−1}
−xS = −x − x^{2} − x^{3} − … − x^{n}

Adding these two equations gives:

(1 − x)S = 1 − x^{n}
S = \frac{1 − x^{n}}{1 − x}

Infinite Geometric Series L11−P. 9

Assume you will live forever ... (always in a good shape of course)

Would you prefer a million dollars today or $50,000 a year? (Yes! infinite money)

The limit of our geometric sum as n tends to infinity is

Theorem If |x| < 1, then ∑_{i=0}^{∞} x^{i} = \frac{1}{1−x}.

∑_{i=0}^{∞} x^{i} = lim_{n→∞} ∑_{i=0}^{n−1} x^{i}
= lim_{n→∞} \frac{1 − x^{n}}{1 − x}
= \frac{1}{1 − x}

Note that in evaluating the limit the x^{n} term vanishes since we assumed that |x| < 1. x = 1/(1 + p) < 1, so the theorem applies. Substituting for x, we get an annuity value of

V = m · \frac{1}{1 − x}

= m · \frac{1}{1 − 1/(1 + p)}

= m · \frac{1 + p}{(1 + p) − 1}

= m · \frac{1 + p}{p}

Plugging in m = $50, 000 and p = 0.8 gives only V = $675, 000. Amazingly, a million dollars today is worth much more than $50, 000 paid every year forever!

Because with a million dollars today in the bank earning 8% interest, We could spend $80, 000 a year forever.

Sums of Decreasing Geometric Series L11−P. 11

1 + 1/2 + 1/4 + 1/8 + … = ∑_{i=0}^{∞}(1/2)^{i}
= \frac{1}{1 − (1/2)}
= 2
0.999999999 … = 0.9 ∑_{i=0}^{∞}(1/10)^{i}
= 0.9\frac{1}{1 − 1/10}
= 0.9\frac{10}{9}
= 1
1 − 1/2 + 1/4 − 1/8 + … = ∑_{i=0}^{∞}(−1/2)^{i}
= \frac{1}{1 − (−1/2)}
= 2/3

Sums of Increasing Geometric Series L11−P. 12

1 + 2 + 4 + 8 + … + 2^{n−1} = ∑_{i=0}^{n−1} 2^{i}
= \frac{1 − 2^{n}}{1 − 2}
= 2^{n} − 1
1 + 3 + 9 + 27 + … + 3^{n−1} = ∑_{i=0}^{n−1} 3^{i}
= \frac{1 − 3^{n}}{1 − 3}
= \frac{3^{n} − 1}{2}

Rule of thumb: approximately equal to the greatest term value Related Sums L11−P. 13

there are cases in which we need to work harder... ∑_{i=1}^{n} ix^{i} = x + 2x^{2} + 3x^{3} + … + nx^{n} \frac{d}{dx} ∑_{i=0}^{n} x^{i} = \frac{d}{dx} \frac{1−x^{n+1}}{1−x}

∑_{i=0}^{n} ix^{i−1} = \frac{−(n+1)x^{n}(1−x)−(−1)(1−x^{n+1})}{(1−x)^{2}} = \frac{−(n+1)x^{n}+(n+1)x^{n+1}+1−x^{n+1}}{(1−x)^{2}}

= \frac{1−(n+1)x^{n}+nx^{n+1}}{(1−x)^{2}}

Now we multiply be x to have: ∑_{i=0}^{n} ix^{i} = \frac{x−(n+1)x^{n+1}+nx^{n+2}}{(1−x)^{2}} Good practice to verify by induction, at least examples... In case n = ∞, we may conclude: Theorem: If |x| < 1, then ∑_{i=0}^{∞} ix^{i} = \frac{x}{(1−x)^{2}}.

Book Stacking Example L11−P. 14

If n books are stacked on a table, how far can the top book overhang the edge without the whole stack falling over?

Book length = 2, book mass identical. 1 ≤ i ≤ n, d_{i} is the distance that book 0 extends beyond the right end of book i. The table is regarded as book n + 1 A stack of books is stable iff for 1 ≤ k ≤ n, the center of mass for the top k books lies above the (k + 1)-st book.

Greedy strategy: The book 1 as far as possible on the book 2 The two top books as far as possible on book 3 And so on... d_{k} is the center of the mass of the top k books

The center of mass of book i is at distance d_{i}+1 to the left of the top book.

The center of mass of the top k books (0, …, k− 1) is the average of this values:

\frac{(d_{k−1}+1)+(d_{k−2}+1)+···+(d_{0}+1)}{k}

By our greedy choice: d_{k} = \frac{(d_{k−1}+1)+(d_{k−2}+1)+···+(d_{0}+1)}{k}

Or: kd_{k} = d_{k−1} + d_{k−2} + ⋯ + d_{0} + k Now algebra: (k − 1)d_{k−1} = d_{k−2} + d_{k−3} + ⋯ + d_{0} + k − 1

Substraction of the above formulas: kd_{k} − (k − 1)d_{k−1} = d_{k−1} + 1 or, d_{k} = d_{k−1} + 1/k d_{k} = d_{k−2} + 1/(k − 1) + 1/k ... d_{k} = 1 + 1/2 + ⋯ + 1/(k − 1) + 1/k

We cannot do better since we mast have the centers located such that

d_{k} ≤ \frac{(d_{k−1}+1)+(d_{k−2}+1)+···+(d_{0}+1)}{k}

Evaluating the Sum — The Integral Method L11−P. 18

using induction we can prove that d_{k} is largest possible. n-th Harmonic number H_{n} is:

∑{n \atop i=1} \frac{1}{i}

H_{1} = 1, H_{2} = 1 + \frac{1}{2} = \frac{3}{2}, H_{3} = 1 + \frac{1}{2} + \frac{1}{3} = \frac{11}{16}, H_{4} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} = \frac{25}{12}.

H_{4} > 2 thus — the total extension of a 4-book stack is greater than one full book!

What about extension of 100 books? Look for H_{l} ≥ 200, Can we have a “closed form”? No close form is known The area under the “stairstep” curve over the interval [0, n] is equal to H_{n} = ∑_{i=1}^{n} 1/i.

1/x ≥ the stairstep function 1/(x + 1) ≤ the stairstep function

H_{n} ≤ 1 + ∫_{1}^{n} \frac{1}{x} dx = 1 + ln n H_{n} ≥ ∫_{0}^{n} \frac{1}{x+1} dx = ∫_{1}^{n+1} \frac{1}{x} dx = ln(n + 1)

We need approximately e^{2}00 books, which is a 86 digits number!.

Harmonic Numbers, Cont. L11−P. 20

Better approximation —

H_{n} = ln n + γ + \frac{1}{2n} + \frac{1}{12n^{2}} + \frac{ϵ(n)}{120n^{4}}

γ = 0.577215664 … called Euler’s constant ϵ(n) is between 0 and 1 for all n.

Shorthand H_{n} ∼ ln n indicates that the leading term of H_{n} is ln n.

f(n) ∼ g(n) means that lim_{n→∞} \frac{f(n)}{g(n)} → 1.

∼ notation is useful when we do not care about lower order terms.

For example, if n = 100, then we can compute H(n) to great precision using only the two leading terms:

|H_{n}−ln n−γ| ≤ |\frac{1}{200} − \frac{1}{120000} + \frac{1}{120·100^{4}}| < \frac{1}{200}