This week’s Riddler Express is a short problem about infinite series. Let’s dig in! (I paraphrased the question)
You and your infinitely many friends are sharing a cake, and you come up with several different methods of splitting it.
- Friend 1 takes half of the cake, Friend 2 takes a third of what remains, Friend 3 takes a quarter of what remains after Friend 2, Friend 4 takes a fifth of what remains after Friend 3, and so on.
- Friend 1 takes $1/2^2$ (or one-quarter) of the cake, Friend 2 takes $1/3^2$ (or one-ninth) of what remains, Friend 3 takes $1/4^2$ of what remains after Friend 3, and so on.
- Same as previous, with even denominators only: Friend 1 takes $1/2^2$ of the cake, Friend 2 takes $1/4^2$ of what remains, Friend 3 takes $1/6^2$ of what remains after Friend 2, and so on.
For each of these methods, after your infinitely many friends take their respective pieces, how much cake is left?
Here is my solution
[Show Solution]
For each different method, let’s call $x_n$ the amount of cake remaining after the first $n$ friends have taken their share. Since we start with a full cake, $x_0=1$. The amount of cake remaining after all friends have taken their share is therefore $\lim_{n\to\infty} x_n$.
Method 1
In this method, Friend number $n$ takes $\frac{1}{n+1}$ of what remains, which is $\frac{1}{n+1}x_{n-1}$. After this happens, the amount of cake remaining is:
\[
x_n = x_{n-1}-\frac{1}{n+1}x_{n-1} = \left(1-\frac{1}{n+1}\right)x_{n-1}.
\]The net result is therefore:
\begin{align}
x_n &= \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)\cdots\left(1-\frac{1}{n+1}\right) \\
&= \left(\frac{1}{2}\right)\left(\frac{2}{3}\right)\left(\frac{3}{4}\right)\cdots\left(\frac{n}{n+1}\right) \\
&= \left(\frac{1}{\bcancel{2}}\right)\left(\frac{\bcancel{2}}{\bcancel{3}}\right)\left(\frac{\bcancel{3}}{\bcancel{4}}\right)\cdots\left(\frac{\bcancel{n}}{n+1}\right) \\
&= \frac{1}{n+1}
\end{align}This is an example of a telescoping series; all the terms in the middle cancel out and we are left with $\frac{1}{n+1}$ of the cake after all friends have gone. Unfortunately, this tends to zero as $n\to\infty$, so with this method, there will be no cake left after all friends have gone!
Method 2
In this method, Friend number $n$ takes $\frac{1}{(n+1)^2}$ of what remains. Using an approach similar to the previous method, we are left with:
\begin{align}
x_n &= \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{4^2}\right)\cdots\left(1-\frac{1}{(n+1)^2}\right) \\
&= \left(\frac{2^2-1}{2^2}\right)\left(\frac{3^2-1}{3^2}\right)\left(\frac{4^2-1}{4^2}\right)\cdots \left(\frac{(n+1)^2-1}{(n+1)^2}\right) \\
&= \left(\frac{1\cdot 3}{2 \cdot 2}\right)\left(\frac{2\cdot 4}{3 \cdot 3}\right)\left(\frac{3\cdot 5}{4\cdot 4}\right)\cdots \left(\frac{n\cdot(n+2)}{(n+1)(n+1)}\right) \\
&= \left(\frac{1\cdot \bcancel{3}}{2 \cdot \bcancel{2}}\right)\left(\frac{\bcancel{2}\cdot \bcancel{4}}{\bcancel{3} \cdot \bcancel{3}}\right)\left(\frac{\bcancel{3}\cdot \bcancel{5}}{\bcancel{4}\cdot \bcancel{4}}\right)\cdots \Biggl(\frac{\bcancel{n}\cdot(n+2)}{\bcancel{(n+1)}(n+1)}\Biggr) \\
&= \frac{n+2}{2(n+1)}.
\end{align}In the third step, we used the difference of squares formula $n^2-1 = (n-1)(n+1)$ to again obtain a telescoping series. This time, however, the sum is $\frac{n+2}{2(n+1)}$, for which the limit $n\to\infty$ is $\frac{1}{2}$. So half of the cake is left after all friends have gone.
Method 3
In this method, Friend number $n$ takes $\frac{1}{(2n)^2}$ of what remains. Again using an approach similar to the previous methods, we obtain.
\begin{align}
x_n &= \left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{4^2}\right)\left(1-\frac{1}{6^2}\right)\cdots\left(1-\frac{1}{(2n)^2}\right).
\end{align}While it looks deceptively similar to the two previous examples solved above, this infinite product is substantially more complicated since there is no telescoping. There is a way to approach this using calculus, but I will instead show a proof using complex analysis that I think is a bit more intuitive.
Every polynomial $p(z)$ of degree $n$ can be factored as $p(z)=a(z-c_1)\cdots(z-c_n)$ where the $c_k$ are zeros of the polynomial (they may be complex numbers). This result can be extended to the case where $p(z)$ is an infinite polynomial with infinitely many zeros. This is known as the Weierstrass factorization theorem. Roughly speaking, if $f(z)$ is an entire function (it must have a power series expansion that is valid everywhere), then we can write it as an infinite product $f(z)=a(z-c_1)(z-c_2)\cdots$ where the $c_k$ are zeros of the infinite polynomial.
Consider the function $f(z) = \frac{\sin(\pi z)}{\pi z}$. This is an entire function because $\sin(\pi z)$ has a power series that is valid everywhere and it has no constant term (recall $\sin(x) = x-\frac{1}{3!}x^3+\frac{1}{5!}x^5-\cdots$) so we can divide through by $\pi z$ and we get another valid power series. The places where $f(z)=0$ correspond to $z \in \{\pm1,\pm2,\pm3,\dots\}$. Note also that $f(0) = \lim_{z\to 0} \frac{\sin(\pi z)}{\pi z} = 1$. By the Weierstrass factorization theorem (I’m skipping some technical details here), we can write:
\begin{align}
f(z) &= a(1-z)(1+z)\left(1-\frac{z}{2}\right)\left(1+\frac{z}{2}\right)\left(1-\frac{z}{3}\right)\left(1+\frac{z}{3}\right)\cdots \\
&= a\left(1-z^2\right)\left(1-\frac{z^2}{2^2}\right)\left(1-\frac{z^2}{3^2}\right)\cdots
\end{align}Since $f(0) = 1$, it must be the case that $a=1$. So we have the series:
\[
\frac{\sin(\pi z)}{\pi z} = \left(1-z^2\right)\left(1-\frac{z^2}{2^2}\right)\left(1-\frac{z^2}{3^2}\right)\cdots.
\]This is known as the Euler infinite product representation for the sinc function. Substituting $z=\frac{1}{2}$, the infinite product becomes exactly the one we wanted to evaluate for how much cake is left:
\[
\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{4^2}\right)\left(1-\frac{1}{6^2}\right)\cdots = \frac{2}{\pi} \approx 0.6366.
\]This infinite product (or its inverse, rather) also has a name; it’s called the Wallis product.
Bonus: Odd-numbered terms
As a side note, if we only keep the odd-numbered terms of the product, we obtain:
\[
\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\left(1-\frac{1}{7^2}\right)\cdots = \frac{\pi}{4} \approx 0.7854.
\]This can be proved using a similar approach, this time with the function:
\[
\cos\left(\frac{\pi z}{2}\right) = (1-z^2)\left(1-\frac{z^2}{3^2}\right)\left(1-\frac{z^2}{5^2}\right)\left(1-\frac{z^2}{7^2}\right)\cdots
\]It then follows that:
\[
\left(1-\frac{1}{3^2}\right)\left(1-\frac{1}{5^2}\right)\left(1-\frac{1}{7^2}\right)\cdots
= \lim_{z\to 1} \frac{\cos\left(\frac{\pi z}{2}\right)}{1-z^2} = \frac{\pi}{4}
\]As a sanity check, we found that using the even terms gives $\frac{2}{\pi}$ and using the odd terms gives $\frac{\pi}{4}$. So using all the terms gives $\frac{2}{\pi}\cdot \frac{\pi}{4} = \frac{1}{2}$, which is what we found using “Method 2”!
Your solution to part 3 is very nice.
I found a rather clumsier approach: there is an explicit expression for x_n:
x_n = ( (2n)!)^2 (2n+1) / ( 2^(4n) (n!)^4 )
which you can prove by induction. We find the large-n limit using Stirling’s approximation.