Nested Functions

Nested functions are expressions such as nested radicals and continued fractions involving infinitely recursive expressions. Examples include

$$\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{\cdots}}}} \qquad \text{and} \qquad 1+\frac2{2+\frac3{3+\frac4{4+\ddots}}}.$$

A sufficiently general and natural definition of nested function, such as the one given below, includes more familiar expressions such as infinite series and infinite products as well.

Determining the value of nested functions when they converge leads to many striking identities. Some of the most beautiful of these are due to the famous Indian mathematician Srinivasa Ramanujan (1887-1920).

Nested radicals involve recursive expressions with repeated square roots. A common problem-solving strategy for evaluating nested radicals is to find a copy of the expression inside itself.

Find the value of

$$\sqrt{n+\sqrt{n+\sqrt{n+\cdots}}},$$

assuming it converges.

---

Call this $x$; then $x = \sqrt{n+x}$. So $x^2-x-n = 0$. By the quadratic formula, $x = \frac{1\pm\sqrt{4n+1}}2$, and clearly the $+$ sign is indicated since $x$ should be positive, so we get $x = \frac{1 + \sqrt{4n+1}}2$. $_\square$

This approach can be directly applied to the following problem:

Some nested functions require more elaborate manipulations.

Let $a$ and $b$ be positive real numbers. Show that

$$a+b = \sqrt{b^2+a\sqrt{b^2+(a+b)\sqrt{b^2+(a+2b)\sqrt{\cdots}}}}$$

if it converges. This identity is due to Ramanujan.

---

Since $(b+x)^2 = b^2+ 2bx+x^2 = b^2 + x\big(b + (x+b)\big)$, taking square roots gives

$$b+x = \sqrt{b^2+x\big(b+(x+b)\big)}.$$

The idea is to apply this expression repeatedly, with $x=a,a+b,a+2b,\ldots$.

Write

$$\begin{aligned} b+a &= \sqrt{b^2+a(\color{#D61F06}{b+a+b})} \qquad \text{(plugging in } x=a\text{)} \\ &= \sqrt{b^2+a\sqrt{b^2+(a+b)(\color{#D61F06}{b+a+2b})}} \qquad \text{(plugging in } x=a+b\text{)} \\ &= \sqrt{b^2+a\sqrt{b^2+(a+b)\sqrt{b^2+(a+2b)(\color{#D61F06}{b+a+3b})}}}. \qquad \text{(plugging in } x=a+2b\text{)} \\ \end{aligned}$$

and so on. $_\square$

Use the identity $(2^n+x)^2 = 4^n+x(2^{n+1}+x)$ to evaluate

$$\sqrt{4+\sqrt{16+\sqrt{64+\sqrt{\cdots}}}}.$$

---

Take the square root of both sides of the identity to get

$$2^n+x = \sqrt{4^n+x(2^{n+1}+x)}.$$

This identity works for any integer $n$; replacing $n$ with $n+1$ gives

$$2^{n+1}+x = \sqrt{4^{n+1}+x(2^{n+2}+x)}.$$

Note that $2^{n+1}+x$ was inside the first square root, so applying the identity repeatedly (increasing the exponent by 1 each time) leads to an infinite nested radical:

$$\begin{aligned} 2^n+x &= \sqrt{4^n+x(\color{#D61F06}{2^{n+1}+x})} \\ &= \sqrt{4^n+x\sqrt{4^{n+1}+x(\color{#D61F06}{2^{n+2}+x})}} \\ &= \sqrt{4^n+x\sqrt{4^{n+1}+x\sqrt{4^{n+2}+x(\color{#D61F06}{2^{n+3}+x})}}}. \end{aligned}$$

The identity is applied to the quantities in red, replacing $n$ with $n+1$, then $n+2$, and so on. This gives an expression of the form

$$2^n+x = \sqrt{4^n+x\sqrt{4^{n+1}+x\sqrt{4^{n+2}+x\sqrt{\cdots}}}}.$$

When $n = x = 1,$ we get

$$3 = \sqrt{4+\sqrt{16+\sqrt{64+\sqrt{\cdots}}}}.\ _\square$$

The strategy of looking for copies of a nested function inside itself works in other contexts as well.

$$\large x = 6+\frac1{2+\frac1{2+\frac1{12+\frac1{2+\frac1{2+\frac1{12+\cdots}}}}}}$$

Given the above, find $x.$

---

We have

$$\begin{aligned} x-6 &= \frac1{2+\frac1{2+\frac1{12+(x-6)}}} \\ &= \frac1{2+\frac1{2+\frac1{x+6}}} \\ &= \frac1{2+\frac{x+6}{2x+13}}\\ &= \frac{2x+13}{5x+32}\\ 5x^2+2x-192 &= 2x+13 \\ x^2 &= 41, \end{aligned}$$

and $x$ is clearly positive. Therefore, $x = \sqrt{41}$. $_\square$

Find

$$\sqrt{14+\sqrt[4]{14+\sqrt[4]{14+\sqrt[4]{\cdots}}}}.$$

---

Call the expression $x$. Then $x = \sqrt{14+\sqrt{x}},$ or $x^2=14+\sqrt{x}$. The graphs of $y = x^2$ and $y = 14+\sqrt{x}$ intersect in exactly one place, and by inspection it happens when $x = 4$. $_\square$

Nested radicals and continued fractions can be considered as two special cases of the general definition, which includes quite a few familiar expressions as other special cases as well.

A nested function is an expression of the form

$$x_0 + y_0\Big(x_1+y_1\big(x_2+y_2(\cdots)^p\big)^p\Big)^p$$

for some real numbers $p, x_i, y_i$. We say it converges if the sequence of partial expressions

$$x_0+y_0\Big(x_1+y_1\big(x_2+y_2(\cdots+y_{k-1})^p\cdots\big)^p\Big)^p$$

converges.

Notice the following:

• If $p=1$ and $y_i = 1$, the nested function is an infinite sum of the $x_i$.
• If $p = 1$ and $x_i = 0$, the nested function is an infinite product of the $y_i$.
• If $p = -1$, the nested function is a continued fraction $$x_0+\frac{y_0}{x_1+\frac{y_1}{x_2+\cdots}}.$$
• If $p = \frac12$, the nested function is of the form $$x_0+y_0\sqrt{x_1+y_1\sqrt{x_2+\cdots}}.$$

It is generally not hard to show that nested radicals of the kind considered above converge, as the sequence of partial expressions is often monotonically increasing and bounded above by the proposed limit. (The sequence of partial expressions is what is obtained by replacing the red terms in the above examples by 1.) Showing that the sequence converges to the expected limit is usually harder but straightforward.

A theorem of Herschfeld (1935) states that for a nested function with $0 < p < 1$ and $y_i = 1$, the nested power $x_0+\Big(x_1+\big(x_2+(\cdots)^p\big)^p\Big)^p$ converges if and only if $x_i^{p^i}$ is a bounded infinite sequence of real numbers.