## Function converges to square root, but why?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Coding
Posts: 47
Joined: Thu Sep 15, 2011 6:59 pm UTC

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

I think the Fibonacci sequence is neat, so today I made this up:
$f(1) = f(2) = 1$$f(n) = \frac{1}{f(n-1)} + \frac{1}{f(n-2)}$
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:
$f(n) = \frac{2}{f(n-1)} + \frac{2}{f(n-2)}$
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,
$f(n) = \frac{a}{f(n-1)} + \frac{b}{f(n-2)}$
seems to converge to sqrt(a + b) as the number of iterations increases. But why does it do that?

[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.
@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!

Dopefish
Posts: 855
Joined: Sun Sep 20, 2009 5:46 am UTC
Location: The Well of Wishes

### 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.)

Coding
Posts: 47
Joined: Thu Sep 15, 2011 6:59 pm UTC

### 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.

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

### 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.

Timefly
Posts: 56
Joined: Sun Nov 14, 2010 7:30 pm UTC

### 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: 26739
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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Sagekilla
Posts: 382
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### 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).
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.