Book Notes: Solving Problems with Sums and Series
This is a problem I found reading Elementary Real Analysis by M. Bruckner, Thomson and J. Bruckner.
I was on a plane from Berlin to Madrid, doing some reading over the 2-hour flight. I had found the chapter about series and sums cumbersome and headed to the exercises section with no expectations.
I found this figure and problem very intriguing. I wanted to figure it out before landing. I have no doubt that mathematically inclined readers may have already found the solution. I had to work for it and will share my thinking process in this blog post.
If you are, like me, interested in refreshing your mathematical knowledge, I would strongly recommend this textbook.
Starting Out
As a Computer Scientist, my first intuition was to find a lower and upper bound of the solution. At first glance, we know that the black region must be between \(1/4\) and \(1/2\) of the area of the square.
Why? Because \(1/4\) is the area of the largest black region, and half of the square is already white (top-left and bottom-right fourths).
So far, so good, but we have not made much progress.
For the rest of this article, I will assume that this square has a side of length \(1\) and area of \(1\). Please do not ask me about the length of its diagonal; this is for another blog post.
Representing the Black Region as an Infinite Sum
Yes, the words infinite sums sound much scarier than they are.
The black region can be represented as the following sum:
\[ \frac{1}{4} + \frac{1}{4} \cdot \frac{1}{4} + \frac{1}{4} \cdot \frac{1}{4} \cdot \frac{1}{4} + \dots \]
Why? Because the first black square is one-fourth of the total square. The second is one-fourth of a fourth of the square. The third is one-fourth of this fourth of a fourth, and so on.
This can be more compactly represented using exponents, with \(n\) a very large number:
\[ \frac{1}{4} + \left(\frac{1}{4}\right)^2 + \left(\frac{1}{4}\right)^3 + \dots + \left(\frac{1}{4}\right)^n \]
But how do we evaluate this sum as \(n\) gets very large and close to infinity?
Note: this will remind mathematically inclined readers of a geometric series.
We could find this result with clever manipulation. When multiplying this expression by \(\left(1 - \frac{1}{4}\right)\), we get to a sum that is much easier to evaluate:
\[ \left(1 - \frac{1}{4}\right) \left(\frac{1}{4} + \left(\frac{1}{4}\right)^2 + \left(\frac{1}{4}\right)^3 + \dots + \left(\frac{1}{4}\right)^n\right) \]
\[ = \left(\frac{1}{4} - \left(\frac{1}{4}\right)^2\right) + \left(\left(\frac{1}{4}\right)^2 - \left(\frac{1}{4}\right)^3\right) + \dots + \left(\left(\frac{1}{4}\right)^n - \left(\frac{1}{4}\right)^{n+1}\right) \]
But why did we multiply this by \(\left(1-\frac{1}{4}\right)\)? Wasn’t this exercise already complicated enough? Just bear with me for another paragraph.
What we have now obtained is a telescoping sum. You may notice that most terms of this sum cancel out:
\[ \left(\frac{1}{4} - \left(\frac{1}{4}\right)^2\right) + \left(\left(\frac{1}{4}\right)^2 - \left(\frac{1}{4}\right)^3\right) + \dots + \left(\left(\frac{1}{4}\right)^n - \left(\frac{1}{4}\right)^{n+1}\right) \]
What I mean that cancel out is that we both add and subtract the same number in the formula. For example, \(\left(\frac{1}{4}\right)^2\) is both subtracted then added. The same applies to most terms in the above formula, until we are only left with:
\[ \frac{1}{4} - \left(\frac{1}{4}\right)^{n+1} \]
Taking a step back, we started with:
\[ \text{Black region} = \frac{1}{4} + \left(\frac{1}{4}\right)^2 + \left(\frac{1}{4}\right)^3 + \dots + \left(\frac{1}{4}\right)^n \]
Multiplying both sides by \(\left(1-\frac{1}{4}\right)\), we get:
\[ \left(1-\frac{1}{4}\right) \cdot \text{Black region} = \frac{1}{4} - \left(\frac{1}{4}\right)^{n+1} \]
\[ \text{Black region} = \frac{\frac{1}{4} - \left(\frac{1}{4}\right)^{n+1}}{1-\frac{1}{4}} \]
This already looks much simpler than an infinite sum, but we are not done yet.
To Infinity and Beyond
We still need to evaluate the above formula as \(n\) grows towards infinity. In mathematics, we note this as:
\[ \lim_{n \to \infty} \frac{\frac{1}{4} - \left(\frac{1}{4}\right)^{n+1}}{1-\frac{1}{4}} \]
When \(n\) grows very large, \(\left(\frac{1}{4}\right)^{n+1}\) will get very close to \(0\). If you do not believe me, you can put \(\left(\frac{1}{4}\right)^{10}\) in your calculator and come back to this article. Spoiler: it is about \(0.0000009\).
So, as \(n\) grows very large, much larger than \(10\), we get:
\[ \lim_{n \to \infty} \frac{\frac{1}{4} - \left(\frac{1}{4}\right)^{n+1}}{1-\frac{1}{4}} = \frac{\frac{1}{4}}{1-\frac{1}{4}} = \frac{1}{3} \]
The area of the black region. How incredible is this?
If you do not believe me, you can run this Python code snippet that will sum \(\frac{1}{4} + \left(\frac{1}{4}\right)^2 + \left(\frac{1}{4}\right)^3 + \dots + \left(\frac{1}{4}\right)^n\) with \(n = 10^6\):
n = 10**6
result = sum((1/4)**i for i in range(1, n+1))
print(result)Final Thoughts
Going over this, I was fascinated by the idea of evaluating the infinite. Making the infinite finite, or finding a way to exploit the regularity of a system to avoid running cumbersome calculations.
If this felt exciting, I would recommend reading Elementary Real Analysis and exploring this topic further.
Beyond mathematics, this shows us the power of exploiting patterns and regularities to reduce complexity in the world. A beautiful journey.