Solution: ‘Puzzles Inspired by Ramanujan’
Our July Insights column was inspired by the mathematics of the phenomenal 20th-century number theorist Srinivasa Ramanujan, whose romantic and tragic life story was the subject of the recent film The Man Who Knew Infinity. Ramanujan’s mentor, G. H. Hardy, compared his mathematical prowess to that of Euler and Jacobi, two of the greatest mathematicians of all time. Ramanujan produced magical mathematical theorems seemingly out of thin air that yielded unexpected new connections, like the formula shown below, which links the three famous constants phi (the golden ratio), e (the base of natural logarithms) and π, using an infinite product this time rather than the sum we displayed in the puzzle column. Many thanks to David for citing this formula.
\(\phi= e^{\pi/6} \prod_{k=1}^\infty \frac{1+e^{-5(2k-1)\pi}}{1+e^{-(2k-1)\pi}}\)
Like the above equation, many of Ramanujan’s results involved infinite sums and products that were truly novel and sometimes intimidating even to professional mathematicians. My goal here was to take simple results related to Ramanujan’s work and make them accessible to readers familiar with no more than high school algebra. If, like most people, you find your eyes glazing over when you see infinite nested radicals or infinite continued fractions, I hope this column and the informal explanations below will give you a glimmer of understanding.
- Our first question is to prove the following equation involving an infinite nested radical. In 1911, Ramanujan sent the right-hand side of the following equation to a mathematical journal as a puzzle:
\(3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+5\sqrt{\cdots}}}}}\)
How can you prove this?
All you need to prove this is the following elementary result:
(x + 1)2 = x2 + 2x + 1 = x(x + 2) + 1
Rearrange the terms to get:
(x + 1)2 = 1 + x(x + 2)
Now if we substitute 2, 3 and 4 for x, we get:
32 = 1 + 2(4), 42 = 1 + 3(5), 52 = 1 + 4(6)…
If we take the square roots of both sides of these equations, we get:
\(3 = \sqrt{1+2(4)}\) (Equation 1)
\(4 = \sqrt{1+3(5)}\) (Equation 2)
\(5 = \sqrt{1+4(6)}\) (Equation 3)
\(6 = \sqrt{1+5(7)}\) (Equation 4)
and so on …
Replacing the (4) in Equation 1 with the right-hand side of Equation 2, we get:
\(3 = \sqrt{1+2\sqrt{1+3(5)}}\)
Now replace the (5) above with the right-hand side of Equation 3 to get:
\(3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4(6)}}}\)
Repeat the same procedure with the next equation:
\(3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+5(7)}}}}\)
It is easy to see that we can continue to replace the last integer in parentheses with the right-hand side of the next equation, so the process can be carried out recursively to infinity. So we can replace the 7 with an ellipsis (…) to show that the process can be repeated indefinitely, thus proving the correctness of the equation.
\(3 = \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+5\sqrt{\cdots}}}}}\)
OK, if you were new to this and had an aha! moment, enjoy the feeling. But we have to put in a strong caveat. As was pointed out by Barbara with a counterexample, the kind of infinite substitution we can do in this and the next problem are not necessarily valid in every case. We’ve seen how the gas pedal works, and now we need to know about the brakes so that in our exhilaration we don’t crash on the mathematical highway! Specifically, we need to be sure that the infinite expression is convergent. This is usually a task for a professional mathematician. We have to apply rigorous tests of convergence that can be applied in specific cases, as in the infinite nested radicals here. In the current case, we can relax — the expression does converge. Here’s a simple informal way to check: Truncate the infinite expression at various points. We can go from left to right, lifting away everything under successive square root signs, leaving only 1, 2, 3 radicals remaining successively, and check the values. In the above case, the values we get are 1.73, 2.24, 2.56, 2.76, 2.87, … — the differences do indeed diminish and approach 3 as we add successive terms.
Ramanujan obtained a general expression using three variables that can generate an infinite number of such equations, like the ones sent in by some readers. Just define f(x) = x + n + a, giving f(x)2= ax + (n + a)2 + x f(x + n). Now you can carry out the same recursive trick we did above for any values of x, n and a. Our example above is obtained if we set a = 0, n = 1 and x = 2. Have fun generating your own infinite nested radicals!
- In our second question, we use basic algebra to prove that the famous golden ratio, phi, is equal to the infinite continued fraction shown below.
The neat thing about the continued fraction on the right is that it is self-similar all the way to infinity. The continued fraction in the red box is exactly the same as that in the blue box. Setting this equal to x, we get x = 1 + 1/x, which yields x2 – x – 1 = 0.
The solutions to this quadratic equation are:
\(\frac{(1+\sqrt5)}{2}\) and \(\frac{(1-\sqrt5)}{2}\).
Since x must be positive, we reject the second solution.
Again, we can do this only if we are sure that the continued fraction converges. In this case, we can show that no matter at what level we place the blue box, it gives the same quadratic expression. Try it and see!
Continued fractions are truly amazing and, for most people, mysterious mathematical objects. This is really a pity, because just as the natural base for logarithms is e rather than 10, and the natural measure of an angle is radians rather than degrees, the most natural representation of a real number, in a sense, is a continued fraction. Like our other examples, it does not rely on an arbitrary choice of base unit. Continued fractions are well worth studying because they embody deep relationships between numbers. I do think Ramanujan’s mastery of continued fractions had a great deal to do with some of the deep results he discovered in number theory.
First, notice the simplicity of the continued fraction representation: The infinite continued fraction for Φ, the golden ratio, can be compactly written as [1; 1, 1, 1, 1, …]. Contrast this simple, regular pattern to the completely random decimal representation 1.6180339887… Similarly, the continued fraction representation for e is the simple and regular [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …], as are the continued fractions representing the rational powers of e.
Other properties of the continued fraction representation are equally compelling. Let us apply repeated truncation to the above fraction, as we did with our radical in problem 1 above: If we do this after each successive number, we get the fractions 1, 1 + 1/1, 1 + 1/(1 + 1/1) and so on. These are called the convergents of the continued fraction, and they have the values 1, 2, 3/2, 5/3, 8/5, … which are nothing but the successive ratios of neighboring Fibonacci numbers, whose value approaches the golden ratio! (To obtain the values of the convergents of a given continued fraction, you can type the word “Convergents” followed by the compact representation of the fraction, without the dots, in Wolfram Alpha; or use an online continued fraction calculator.) The convergents of the continued fraction whose value is n represent the best possible rational approximation to n in the sense that no fraction with a smaller denominator is closer. It’s no wonder that with his intimate understanding of continued fractions, Ramanujan was able to obtain, a century ago, some incredible approximations to π, like the following:
\(\pi\approx\frac{99^2}{2206\sqrt2}\)
which is accurate to the seventh decimal place. Indeed, some of Ramanujan’s formulas were the basis for computer calculations of unprecedented accuracy some 70 years later. All these things reinforce the sense that when you represent real numbers as continued fractions, you are, in some way, carving the world of numbers at its joints. (I must apologize to the memory of Ramanujan here. This is not an analogy that he, as a vegetarian, would have enjoyed.)
- A certain street has between 50 and 500 houses in a row, numbered 1, 2, 3, 4, … consecutively. There is a certain house on the street such that the sum of all the house numbers to the left side of it is equal to the sum of all the house numbers to its right. Find the number of this house.
The story behind this problem is as follows. A friend of Ramanujan, P. C. Mahalanobis, who was also a student at Cambridge and who later became an eminent statistician, read about this problem while visiting Ramanujan. Ramanujan was in the kitchen, cooking. Mahalanobis solved the problem, and then turned to Ramanujan and said, “Here’s a problem for you.” “What problem? Tell me,” said Ramanujan, still stirring vegetables. Mahalanobis read the problem. Ramanujan immediately said, “Take down the solution.” He then dictated a continuous fraction that expressed all the infinite solutions to the problem if you ignore the constraint of 50 to 500 houses. So as a bonus problem, can you emulate Ramanujan and find a formula that generates this general solution?
As usual, Quanta readers responded magnificently to this puzzle, obtaining the correct answer (house number 204, on a street with 288 houses) using a variety of methods. With simple algebra, it is easy to obtain the equation 2h2 = n(n + 1), where h is the house number, and n is the total number of houses. This is an equation with an infinite number of integer solutions (the general name for an equation requiring integer solutions is Diophantine equation). We now have to find integer solutions with n in the range 50 to 500, which can be done by using a brute-force search using a spreadsheet, or by computer programming, as several readers did. Another approach is to start small — it is quite easy to find solutions to the above equation for small numbers such as h = 1, n = 1 followed by h = 6, n = 8. From this you can find a simple recurrence relation between h and n, or between successive h’s or n’s, using standard techniques for recurrences, as Greg Egan did. This yields all the infinite solutions recursively. Amazingly, Tom Nichols was able to derive a closed-form solution using the time-honored technique of playing with the numerical solutions. Congratulations, Tom! The young Ramanujan would have approved!
The first step to finding the solution without using trial-and-error methods is to recognize that the equation we obtained above can be expressed as a Pell equation of the form nx2 + 1 = y2, as described below. There are two well-known ways to solve these kinds of equations. The first, which doesn’t use continued fractions, is a method based on work done by the Indian mathematician Brahmagupta a thousand years before Pell, and transformed into a general method called the chakravala, or cyclic, method by Bhaskara II in the 12th century. The second method is based on continued fractions, the complete theory of which was perfected by Lagrange in the 18th century.
This brings us back to the bonus question. What is the continued fraction that Ramanujan came up with? Just by inspecting our equation, we can see that the ratio n:h will approach \(\sqrt2\) as n and h increase indefinitely. The continued fraction for \(\sqrt2\) is [1; 2, 2, 2, 2, …]. As Greg Egan described, this does yield the solutions, but not elegantly — you have to perform different operations on the odd and even convergents, and the solutions are not in order. A better approach derives the Pell equation and is described by Christopher Long:
Let there be n houses and let m be the excluded house, then the sum of 1 + … + (m – 1) must equal 1/2 of the sum of (1 + … + n) – m. This gives m(m – 1)/2 = n(n + 1)/4 – m/2 or 2m^2 = n(n + 1). Now complete the square on the right and we have 2m^2 + 1/4 = (n + 1/2)^2; finally, multiply by 4 to get (2n + 1)^2 – 8m^2 = 1. This is equivalent to solving the Pell equation x^2 – 8*y^2 = 1, as x must be odd. Solutions for x, y can be generated from the continued fraction for sqrt(8) = [2; 1, 4, 1, 4, …].
This is definitely a better continued fraction for this problem. The convergents are 2, 3, 14/5, 17/6, 82/29, 99/35, 478/169, 577/204, … The denominators of every even-numbered convergent give the house numbers in succession, and their numerators (n) give the number of houses as (n – 1)/2.
This is good, but is there a better answer that Ramanujan might have come up with? It hasn’t been recorded, and I can’t look into his mind, but there is a more elegant answer. To see it, notice that the ratio 2n + 1 to h in this problem starts out at 3 and must decrease every time in succession — it must get monotonically closer to \(\sqrt8\) as n and h increase. The convergents of the above continued fraction, on the other hand, oscillate from one side of the limit value to the other, which is why its odd-numbered convergents have to be discarded. How can we correct this? Well, there is a noncanonical form of the continued fraction for \(\sqrt8\) that does do that: [3; –6, 6, –6, 6, –6, 6, …]. The convergents of this continued fraction are precisely successive solutions to the problem: 3, 17/6, 99/35, 577/204, etc. Here is how the continued fraction looks when written out in full in elegant, albeit slightly nonstandard, form:
\(3-\frac{1}{6-\frac{1}{6-\frac{1}{6-\frac{1}{6-\frac 1\ddots}}}}\)
From this continued fraction, it is easy to derive the recurrence hn+1 = 6hn – hn-1, which was described by Tom Nichols and Michael, and the corresponding recurrence for n, posted by Sudhir Kumar. From standard continued fraction theory we can easily derive the quadratic equation mentioned by Michael, x2 = 6x – 1. The theory also gives an elegant closed-form solution (\((3+\sqrt8)^k\)) that you can write down directly, just by inspecting the continued fraction. If you carry out this expansion, and gather and add all the like terms, the multiplier of the radical gives h, the house number, and the integer part gives the number 2n + 1, where n is the number of houses. If we want to separate the two, we can obtain the following closed forms from this:
\(2n+1 = \frac{(3+\sqrt8)^k + (3-\sqrt8)^k }{2}\)
and
\(h = \frac{(3+\sqrt8)^k – (3-\sqrt8)^k }{2\sqrt8}\)
The latter is a simpler version of the same closed form obtained by Tom Nichols.
Thank you, everyone, for the great comments. I feel compelled to award two Quanta T-shirts this time: one to Tom Nichols for his discovery of the closed form, and the other to Christopher Long for his solution of the Pell equation. If this column has stimulated your interest in continued fractions, there is an excellent tutorial online.
See you next time for new Insights!
