## Tuesday, July 26, 2016

### Morning Math 2016 - Part II

Continuing from my previous post about what I learned from the PCMI morning math problem sets, this post will focus on various proofs of the geometric series formula. Variations on the geometric series came up many times as we were calculating expected value.

To calculate the sum of a geometric series the following is true:
$$1+\frac {1}{b} + \frac {1}{b^2}+ \frac {1}{b^3}... = \sum_{n=0}^{\infty}r^n = \frac{1}{1-r}$$ where $$\frac{1}{b}=r$$ and $$|r|<1$$.

a) Paper splitting: Say that there are b people and one of the people, the “dealer”, starts with b papers. The dealer proceeds to give each of the other people a paper and keep one for herself. She then splits her paper into b parts, and gives each of the other people one part and keeps one part for herself. She repeats the process until she has no more paper and therefore, her piece of paper is evenly split between the other $$b-1$$ people. Each other person gets  $$1+\frac {1}{b} + \frac {1}{b^2}+ \frac {1}{b^3}...$$ pieces of paper, which has to equal the original piece they got plus the $$\frac{1}{b-1}$$they were given of the dealer’s paper. Then, if you don’t believe intuitively that $$1+\frac{1}{b-1}=\frac{1}{1-\frac{1}{b}}$$, here’s algebraic proof: $$1+\frac{1}{b-1}=\frac{b-1}{b-1}+ \frac{1}{b-1}=\frac{b}{b-1}=\frac{1}{\frac{b-1}{b}}=\frac{1}{\frac{b}{b}-\frac{1}{b}}=\frac{1}{1-\frac{1}{b}}$$.

And here’s a beautiful visual proof that my table group created for when b=4.

b) Algebraic substitution:
$$S=1+r+r^2+r^3+r^4…$$
$$S=1+ r(1+r+r^2+r^3…)$$
$$S=1+rS$$ (Substitute S into the equation above)
$$S-rS=1$$
$$S(1-r)=1$$
$$S=\frac{1}{1-r}$$

c) Algebraic elimination:
$$S=1+r+r^2+r^3+r^4…$$
$$rS=r+r^2+r^3+r^4…$$ (Scale the original equation by r)
$$S-rS=1$$
$$S(1-r)=1$$
$$S=\frac{1}{1-r}$$

d) Recursion:
A dog’s bowl starts filled with 1 liter of water. By the end of each day, the dog has $$\frac{1}{b}$$ of the water it started the day with and the owner adds another liter of water. If this process continues forever, how much water will the bowl eventually always start with?
 Days n Amount of water W(n) 0 1 1 $$\frac{1}{b} + 1$$ 2 $$\frac{1}{b^2} +\frac{1}{b}+1$$ 3 $$\frac{1}{b^3} +\frac{1}{b^2} +\frac{1}{b}+1$$
Recursive formula: $$W(n) = \frac{1}{b}*W(n-1)+1$$
Since we know that this will lead to a steady state, eventually…
$$W = \frac{1}{b}*W+1$$
$$W-\frac{1}{b}*W=1$$
$$W(1-\frac{1}{b})=1$$
$$W=\frac{1}{1-\frac{1}{b}}$$