Nested Radical Recursions

Recently I've been playing with some cool series and recursions, and though I haven't been able to prove anything significant I did come up with some cool results. Below are the two recursions; I'll save the series for my next post. First,

consider

the

recursion

f Hx, pL = H f Hx - 1, pL + f Hx - 2, pLL = 1 p

p

defined

by

f Hx - 1, pL + f Hx - 2, pL .

Notice that when p = 1, the recursion reduces to the fibonacci sequence, f(x)=f(x-1)+f(x-2). A natural question arises with this recursion: what is the limit of the sequence as x®¥? We can use Mathematica to calculate the result for us. (The sequence tends to level off pretty quickly, so I've used x=20 here as a good approximation for the limit.) They are listed below as ordered pairs H p, f @20DL. 2 3 4 5 6 7 8 9 10

1.999755983264744` 1.4142128329386618` 1.2599210337489952` 1.1892071140675122` 1.1486983549008871` 1.1224620482948884` 1.1040895136709459` 1.0905077326645616` 1.080059738892108`

Now, you may not recognize this as anything significant. However, it turns out that the limits are {2, 2,

3

2,

4

2 , ...}. So, we have the relationship

Lim f @n, pD = 2 n®¥

1 p-1

=

p-1

2

Below is a graph of f HxL for p = 2, so you can get an idea of how the sequence is converging.

2

Nested Radical Recursions.nb

2.0

1.8

1.6 Out[11]=

1.4

1.2

2

4

6

8

10

12

I thought there might be a cool way to determine this analytically, but there seems no easy way to analyze the series of values you get from f[x,p]. Take p=2 as an example. Then the values go like this:

Nested Radical Recursions.nb

3

Table@8N@f@x, 2DD, f@x, 2D<, 8x, 1, 7
1.

1

1.41421

2 1+

1.55377

2 +

1.72278

1+

1.81013

2 1+

2 +

2

2 +

1+

2

Out[18]=

2 +

1.8796

1.92087

1+

2 +

2 +

1+

1+

2

2

+

+

1+

2 +

2 +

1+

2

2 +

+

1+

1+

2

2

Often these nested square roots are solveable by some clever algebraic manipulation, but I haven't come up with a method for doing that. The method I would attempt to use works in some simple cases: for example, say we want to find the value of a+

a+

a+

a + ... .Then set x =

a + ... , which gives x 2 = a + x. Solving by the quadratic formula gives x =

1 2

H4 a + 1L, a

numerical value for the nested square root. The "trick" we make use of here is the substitution of our original definition of x, reducing the equation to one in terms of x and a; unfortunately, that's more difficult with the radical defined by Lim f HnL. n®¥

It might also prove interesting to look at the recursions for fractional values of p such as p = 12 , which would correspond to the sequence kHxL = 2 2 2 HkHx - 1L + kHx - 2LL = kHx - 1L + 2 kHx - 1L kHx - 2L + kHx - 2L . Considering that this sequence kHnL looks pretty similar to the Fibonacci Sequence, we might ask if Lim kHn-1L approaches a constant, just n®¥

as

FHnL Lim FHn-1L =Φ, n®¥

the golden ratio (FHnL is the fibonacci series). If we substitute, however, we obtain

kHn-1L2 +2 kHn-1L kHn-2L+kHn-2L2 , which clearly goes to infinity since kHn-1L n®¥ ratio kHnL 2 goes to 1 as n ® ¥, an excersize left to the reader. kHn-1L

Lim

kHnL does. On the other hand, the

p

p

numerical value for the nested square root. The "trick" we make use of here is the substitution of our original definition of x, reducing the equation to one in terms of x and a; unfortunately, that's more 4 Nested Radical Recursions.nb difficult with the radical defined by Lim f HnL. n®¥

It might also prove interesting to look at the recursions for fractional values of p such as p = 12 , which would correspond to the sequence kHxL = 2 2 2 HkHx - 1L + kHx - 2LL = kHx - 1L + 2 kHx - 1L kHx - 2L + kHx - 2L . Considering that this sequence kHnL looks pretty similar to the Fibonacci Sequence, we might ask if Lim kHn-1L approaches a constant, just n®¥

as

FHnL Lim FHn-1L =Φ, n®¥

the golden ratio (FHnL is the fibonacci series). If we substitute, however, we obtain

kHn-1L2 +2 kHn-1L kHn-2L+kHn-2L2 , which clearly goes to infinity since kHn-1L n®¥ ratio kHnL 2 goes to 1 as n ® ¥, an excersize left to the reader. kHn-1L

Lim

kHnL does. On the other hand, the

A simliar recursive function can be considered, defined as g Hx, pL =

p

gHx - 1, pL +

p

gHx - 2, pL .

Below is a table of the limits of g@x, pD as p varies. The table lists ordered pairs H p, g@20DL.

Out[31]=

2 3 4 5 6 7 8 9 10

3.99902 2.82842 2.51984 2.37841 2.2974 2.24492 2.20818 2.18102 2.16012

These, strangely enough, turn out to be 2 times the H p - 1Lst root of 2, i.e. 1

n®¥

1

1+ p-1

Lim gHnL = 2 * 2 p-1 = 2

p

= 2 p-1 =

p-1

2p

This confirms my assumption that gHxL and f HxL are related. Once again, however, I have no simple way to prove this limit to be true. Below is a table of values of g(x,2), to give you a feel for what they look like.

Nested Radical Recursions.nb

In[34]:=

5

TableA9N Ag Hx , 2LE, g Hx , 2L=, 8x , 1, 7<E 1. 2.

1 2 1+

2.41421

2 +

2.96799 1+

3.27656

2 1+

2 +

2

2 +

1+

2

Out[34]=

2 +

3.53291

3.68973

1+

2 +

2 +

1+

1+

2

2

+

+

1+

2 +

2 +

1+

2

2 +

+

1+

1+

2

2 +

2 +

1+

2

My instincts tell me there is some way to analytically determine this value.I know that the Indian mathematician Ramanujan did some intense work with nested radicals, so maybe one of his formulas applies here.