I think the Fibonacci sequence is neat, so today I made this up:

[math]f(1) = f(2) = 1[/math][math]f(n) = \frac{1}{f(n-1)} + \frac{1}{f(n-2)}[/math]

I plug it into a program and get:

2.0

1.5

1.16666666666667

1.52380952380952

1.51339285714286

1.31701696165192

...

1.41422484178857

Hey, looks really close to the square root of 2! I try plugging in differential initial values, even way bigger or smaller, and it still converges to the same value. Then I mess with the formula a bit by putting in new numerators, for example:

[math]f(n) = \frac{2}{f(n-1)} + \frac{2}{f(n-2)}[/math]

Which gives (for initial values 1 and 1):

4.0

2.5

1.3

2.33846153846154

2.39372469635628

1.69078112829643

...

2.00003772872139

No matter what numerators or initial values I use,

[math]f(n) = \frac{a}{f(n-1)} + \frac{b}{f(n-2)}[/math]

seems to converge to sqrt(a + b) as the number of iterations increases. But why does it do that?

## Function converges to square root, but why?

**Moderators:** gmalivuk, Moderators General, Prelates

- [Kreativername]
**Posts:**18**Joined:**Fri Mar 20, 2009 1:57 pm UTC

### Re: Function converges to square root, but why?

The usual trick with recursive series like this is to just substitute the same variable x or something for all instances of f(n-1) etc. so in this case you get:

[imath]x = \frac{a}{x} + \frac{b}{x}[/imath]

and solving for x gives you

[imath]x=sqrt(a+b)[/imath]

So if the series does indeed converge that (+-) is what it is going to converge to. But I haven't checked wether it always converges yet.

[imath]x = \frac{a}{x} + \frac{b}{x}[/imath]

and solving for x gives you

[imath]x=sqrt(a+b)[/imath]

So if the series does indeed converge that (+-) is what it is going to converge to. But I haven't checked wether it always converges yet.

@agitpopblog wrote:I'm a cat in a steel chamber with a Geiger counter, a bit of radioactive substance and hydrocyanic acid. I am the 50 percent!

### Re: Function converges to square root, but why?

Well, if f(n) does converge to something, say L, then lim n->inf f(n) = lim n->inf f(n-1)= lim n->inf f(n-2) = L.

This gives you an equation like L= a/L +b/L, or L^2=a+b, i.e. L =+/- sqrt(a+b).

That's doing things in a rather handwavey way, but you could probably show with a bit of work that the sequence is cauchy (i.e. the difference in subsequent terms approaches zero), and similarly that the sequence is bounded, which is enough to conclude that the limit actually does exist, which would justify the above. The showing it's bounded part is also likely to eliminate one of the possible solutions for L, so you'd be left with L = sqrt(a+b) as you found.

(Also, I'm slow.)

This gives you an equation like L= a/L +b/L, or L^2=a+b, i.e. L =+/- sqrt(a+b).

That's doing things in a rather handwavey way, but you could probably show with a bit of work that the sequence is cauchy (i.e. the difference in subsequent terms approaches zero), and similarly that the sequence is bounded, which is enough to conclude that the limit actually does exist, which would justify the above. The showing it's bounded part is also likely to eliminate one of the possible solutions for L, so you'd be left with L = sqrt(a+b) as you found.

(Also, I'm slow.)

### Re: Function converges to square root, but why?

[Kreativername] wrote:The usual trick with recursive series like this is to just substitute the same variable x or something for all instances of f(n-1) etc. so in this case you get:

[imath]x = \frac{a}{x} + \frac{b}{x}[/imath]

and solving for x gives you

[imath]x=sqrt(a+b)[/imath]

So if the series does indeed converge that (+-) is what it is going to converge to. But I haven't checked wether it always converges yet.

Neat, I didn't know you could just replace them with x like that. Thanks.

### Re: Function converges to square root, but why?

Coding wrote:Neat, I didn't know you could just replace them with x like that. Thanks.

You cannot do that in general. It does not work for general sequences and it is just coincidence that it works in this case.

### Re: Function converges to square root, but why?

korona wrote:Coding wrote:Neat, I didn't know you could just replace them with x like that. Thanks.

You cannot do that in general. It does not work for general sequences and it is just coincidence that it works in this case.

Assuming the sequence is convergent, then it's perfectly reasonable.

- gmalivuk
- GNU Terry Pratchett
**Posts:**26738**Joined:**Wed Feb 28, 2007 6:02 pm UTC**Location:**Here and There-
**Contact:**

### Re: Function converges to square root, but why?

Yeah, in general with limits like this you can prove statements of the form, "If this converges, it converges to L", which can be true regardless of whether or not it converges in the first place. You typically also want it to converge in the first place, of course, which might require a different sort of proof.

### Re: Function converges to square root, but why?

I'd say it more accurately converges to the sum sqrt(abs(k1) + abs(k2)),

where k1 and k2 are the constants in the numerator. If you take k1 = 1,

k2 = -2 you'll see what I mean.

You have to be careful about your choice of k1, k2 and the initial values

f(0) and f(1). If k1 or k2 is less than zero, you may have a ill defined sequence

depending on f(0) and f(1).

where k1 and k2 are the constants in the numerator. If you take k1 = 1,

k2 = -2 you'll see what I mean.

You have to be careful about your choice of k1, k2 and the initial values

f(0) and f(1). If k1 or k2 is less than zero, you may have a ill defined sequence

depending on f(0) and f(1).

http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.

### Who is online

Users browsing this forum: No registered users and 16 guests