Zeno, Revisited

The Greek philosopher Zeno of Elea gets the credit for a number of paradoxes that challenge our intuition about space and time. His dichotomy paradox starts with the observation that in order to go a some fixed distance \(d\), you must first travel half the distance. When you get there, you will have half the distance, or \(\frac{d}{2}\), remaining. To cover that distance, you must first travel half of it and have \(\frac{d}{4}\) remaining. After four of these steps, you will have travelled \[\frac{d}{2} +\frac{d}{4} +\frac{d}{8} +\frac{d}{16} = \frac{15}{16}d\] and still have\(\frac{d}{16}\) to go, as illustrated in Figure 1.

The paradox arises because it seems as if you can never fully reach your destination. No matter how many steps you take, there always seems to be some distance that remains.

Fortunately, with calculus we can prove that the series described by Zeno will converge to \(d\), meaning you indeed can get to your destination. In this challenge, you will code up the original dichotomy series and see that it quickly converges beyond the precision of your computer. You will also be invited to modify your program and see series whose terms look very different but that still converge to the same point.

Basic Challenge

Write a program to calculate how far you would go after 100 of Zeno's dichotomy steps if the distance you want to go is 1 unit. That is, your program should calculate the sum \[\sum_{n=1}^{100}\frac{1}{2^{n}} = \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + \dots + \frac{1}{2^{100}}\] and print the result. If you do this correctly, you will find that your answer is indistinguishable from 1.0 given the finite precision of your computer.

Here is a replit in C++ and one in Python if you want to see how I did it.

Extension Challenge

Zeno suggested that our journey would be made up of steps that each take us halfway to our destination. What if we use some other fraction of the distance?

1. Do a similar calculation to the warm-up, using a fraction bigger than \(\frac{1}{2}\). For example, suppose we choose \(\frac{2}{3}\). Then our calculation looks like
   

   Step	Distance	Total Travelled	Remaining
   1	\(\frac{2}{3}\times 1 = \frac{2}{3}\)	\(\frac{2}{3}\)	\(\frac{1}{3}\)
   2	\(\frac{2}{3}\times \frac{1}{3} = \frac{2}{9}\)	\(\frac{2}{3} + \frac{2}{9} = \frac{8}{9}\)	\(\frac{1}{9}\)
   3	\(\frac{2}{3}\times \frac{1}{9} = \frac{2}{27}\)	\(\frac{8}{9} + \frac{2}{27} = \frac{26}{27}\)	\(\frac{1}{27}\)
   4	\(\frac{2}{3}\times \frac{1}{27} = \frac{2}{81}\)	\(\frac{26}{27} + \frac{2}{81} = \frac{80}{81}\)	\(\frac{1}{81}\)
   \(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)

   
   The first three steps can be visualised as in Figure 2.
   

   

   
   You can program this as the sum \[\sum_{n=1}^{100}\frac{2}{3^{n}} = \frac{2}{3} + \frac{2}{9} + \frac{2}{27} + \dots + \frac{2}{3^{100}}\]
2. What happens if the distance we use is less than half? Suppose we try going only \(\frac{1}{4}\) of the distance remainging each time. Do you think we can make it to the destination?
   

   Step	Distance	Total Travelled	Remaining
   1	\(\frac{1}{4}\times 1 = \frac{1}{4}\)	\(\frac{1}{4}\)	\(\frac{3}{4}\)
   2	\(\frac{1}{4}\times \frac{3}{4} = \frac{3}{16}\)	\(\frac{1}{4} + \frac{3}{16} = \frac{7}{16}\)	\(\frac{9}{16}\)
   3	\(\frac{1}{4}\times \frac{9}{16} = \frac{9}{64}\)	\(\frac{7}{16} + \frac{9}{64} = \frac{37}{64}\)	\(\frac{27}{64}\)
   4	\(\frac{1}{4}\times \frac{27}{64} = \frac{27}{256}\)	\(\frac{37}{64} + \frac{27}{256} = \frac{175}{256}\)	\(\frac{81}{256}\)
   \(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)

   
   Write a program to confirm your guess. Use the sum \[\sum_{n=1}^{100}\frac{3^{n-1}}{4^{n}} = \frac{1}{4} + \frac{3}{16} + \frac{9}{64} + \dots + \frac{3^{99}}{4^{100}}\]

Implementation Notes

In C++, the correct way to calculate an exponential is with the

	  
	    double pow(double base, double exponent);
	  
	

function call. This is found in the cmath library, so you should add it to the #include directives at the top of your file:

	  
	    #include <iostream>
	    #include <cmath>
	  
	

Remember to put any literal values in the correct form:

	  
	    partial_sum += 1.0 / pow(2.0, exponent);
	  
	

Takeaways

This challenge required you to use looping and, if you are programming in C++, to include a standard library. These are essential skills. Well done!

If you programmed these series correctly, you should have seen that they all converge to 1. To me, it is at once mysterious and pleasing that all of the following are true:

\[\sum_{n=1}^{\infty} = \frac{1}{2^{n}} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \dots = 1\] \[\sum_{n=1}^{\infty}\frac{2}{3^{n}} = \frac{2}{3} + \frac{2}{9} + \frac{2}{27} + \frac{2}{81} + \dots = 1\] \[\sum_{n=1}^{\infty}\frac{3^{n-1}}{4^{n}} = \frac{1}{4} + \frac{3}{16} + \frac{9}{64} + \frac{27}{256} + \dots = 1 \]