Function converges to square root, but why?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Function converges to square root, but why?

Postby Coding » Sun Apr 01, 2012 6:06 pm UTC

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?

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

Re: Function converges to square root, but why?

Postby [Kreativername] » Sun Apr 01, 2012 6:58 pm UTC

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!

User avatar
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?

Postby Dopefish » Sun Apr 01, 2012 7:01 pm UTC

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

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

Re: Function converges to square root, but why?

Postby Coding » Sun Apr 01, 2012 7:16 pm UTC

[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?

Postby korona » Sun Apr 01, 2012 7:28 pm UTC

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?

Postby Timefly » Sun Apr 01, 2012 8:16 pm UTC

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.

User avatar
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?

Postby gmalivuk » Sun Apr 01, 2012 9:14 pm UTC

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?

Postby Sagekilla » Sun Apr 01, 2012 10:09 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 16 guests