Waste less time on Facebook — follow Brilliant.

Finding the correct solution in nested iterations problems

This note concerns the logic of why some possible solutions to nested radical problems are incorrect. I would like to warn you it is a somewhat lengthy monologue. Please read on if you are uncertain about the topic. Also, please solve this problem before reading on.

First I would like to thank Pranay Singh for the set Nested Radicals which contains a sizable number of problems relating to infinite nested fractions or radicals. My first math competition was a state geometry competition. In between rounds, there were "just for fun" problems; that is where I saw my first nested radical problem, and it fascinated me. An example of an infinite nested radical problem is \[\text{Find the value of: } \\ x = \sqrt{100 + \sqrt{100 + \sqrt{100 + ...}}}\]

There are a few methods to go about this, but seemingly the most popular is substitution. \[x = \sqrt{100 + x} \\ x^2 = 100 + x \\ ... \\ x = \frac{1}{2}(1 \pm \sqrt{401})\]

This seems like \(x\) could be two different values, but the correct answer is \(x = \frac{1}{2}(1 + \sqrt{401}).\) How does one conclude it must be the positive value? In this case, it's simple. There are three easy ways to prove it:

  1. Substitute the negative solution into the original equation; it will be incorrect.
  2. Reason that \(x\) will be positive, since square root returns positive values.
  3. Reason that \(x\) will be positive, since the result must be positive.

Now I will show a different problem: \[\text{Find the value of:} \\ x = \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{...}}}\] If you are having trouble seeing it, it is the infinite tetration of \(\sqrt{2},\) meaning \(\sqrt{2}\) to the power of \(\sqrt{2}\) to the power of \(\sqrt{2}\) and so on. If you use the popular substitution method, you will see that \(x = 2\) or \(x = 4.\) One of these is incorrect, so how do you choose the correct one? This problem is interesting in that both possible solutions are positive, so we can't use the "\(x\) is positive" reasoning above. In fact, none of the \(3\) methods above will work.

General solution

Let's define "nested iterations problem" as a problem in which you must find the value of some iteration repeated many times. For example, in the first problem, the iteration is to add \(\sqrt{100}\) to the deepest radical. In the second, the iteration is to raise the expression to the power of \(\sqrt{2}.\) With most nested iterations problems, you can define a function \(f(n)\) to equal the value of the expression after \(n\) iterations. For example, \[f(1) = \sqrt{2} \\ f(2) = \sqrt{2}^\sqrt{2} \\ f(3) = \sqrt{2}^{\sqrt{2}^\sqrt{2}}\] Sometimes, you will be able to find a closed form expression for \(f(n).\) Other times, it may not be possible, or it may be too complicated. Either way, the process of finding the correct solution in an infinite iteration problem is easy: \[x = \lim_{n\to\infty}f(n)\] If you have the closed form, you can usually compute this limit. If you do not have the closed form (or if you do not know about limits), you can basically do the same exact thing numerically, by computing \(f(1),\) \(f(2),\) \(f(3),\) \(f(4),\) and so on, until it stably approaches some value. If you apply this method to the second problem, \[f(1) \approx 1.41 \\ f(2) \approx 1.63 \\ f(3) \approx 1.76 \\ f(4) \approx 1.84\] You can continue this process for a while (perhaps with the assistance of Wolfram Alpha) until you are satisfied it is approaching your predicted value. In this case, we proved it must either be \(x = 2\) or \(x = 4,\) and if you repeat this process, it is more clearly approaching \(2,\) so that must be the correct answer.

This method can also show that a real solution doesn't exist, if applicable. If we try the second problem again, but replace \(\sqrt{2}\) with \(\sqrt{3},\) the numerical value just keeps getting uncontrollably larger and larger, to infinity; thus, no solution exists.

As far as I know, this method can solve any infinite nested iterations problem, but I am hoping that someone can provide a problem that cannot be solved this way.

Note by Caleb Townsend
1 year, 7 months ago

No vote yet
1 vote


Sort by:

Top Newest

Log in to reply

Sir ,
Thanks for this note as this is helpful to all of us .
But I still have a query that why \(\sqrt{3}\) would not converge ?
Are there some other values other than \(\sqrt{2}\) on which the expression would converge ? Pranay Singh · 1 year, 7 months ago

Log in to reply

@Pranay Singh The empirical reason why the \(\sqrt{3}\) case does not converge, is that it keeps getting bigger, and bigger, and bigger, all the way to infinity. Theoretically, though, the infinite tetration of a number makes use of the product log function, or the Lambert W-function. The general formula for an infinite tetration on \(a\) is, to my knowledge, \[f(a) = \frac{W(-\ln(a))}{-\ln(a)}\] As an example, we already solved the \(a = \sqrt{2}\) case to be \(2.\) Here's the Wolfram Alpha link verifying that. Then here's the \(\sqrt{3}\) case, which has an imaginary part, showing the tetration doesn't converge; in fact, this is actually only \(1\) of several possible complex results, but if you wanted to find the "correct" complex solution, I think you should choose the one in the link.

Now as for the domain of convergence: other values than \(a = \sqrt{2}\) work as well; \((\sqrt{5}/2),\) \((11/10),\) and \((e/2),\) to name a few. \[\text{Im}(f(a)) = 0\ \text{ when }\ 0 < a \leq e^{1/e}\]

Note that \(f(1)\) is indeterminate, but we can still assign \(f(1) = 1\) since \(1^{1^{1^{...}}} = 1.\) So the domain of convergence is

\[a\in(0, e^{1/e}]\]

Lastly, here's the graph illustrating that. The maximum convergent value is \(f(e^{1/e}) = e,\) interestingly enough. And here's a graph showing only the convergent values (no, that's not a vertical asymptote on the right! it maxes out at \(e\) then goes back down.) Caleb Townsend · 1 year, 7 months ago

Log in to reply

@Caleb Townsend Thanks sir ,

can you help solving me this query ?
Is this Proof correct ? Pranay Singh · 1 year, 7 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...