To add comments or start new threads please go to the full version of: How To Prove The Below Ratio Always Holds?
PhysForum Science, Physics and Technology Discussion Forums > General Sci-Tech Discussions > Homework Help

Raphie Frank
If one recursively generates number progressions according to the following rule:

A_(n-1) + y*A_(n) = A_(n+1)

The limit at infinity for...

A_(n+1) / A_(n)

... which is the ratio between successive numbers in the progression would seem to be:

(sqrt (y^2 + 4) + y)/2

============================
examples (beginning with (1,1))
============================

For y = 0
A_(n-1) + 0*A_(n) = A_(n+1)
-->
1,1,1,1,1,1,1,1,1,1... (The "Unity" Series)

ratio @ infinity
(sqrt (0^2 + 4) + 0)/2 = 1
============================

For y = 1
A_(n-1) + 1*A_(n) = A_(n+1)
-->
1,1,2,3,5,8,13,21,34,55... (The Fibonacci Series)

ratio @ infinity
(sqrt (1^2 + 4) + 1)/2 = phi
============================

For y = 2
A_(n-1) + 2*A_(n) = A_(n+1)
-->
1,1,2,5,12,29,70,169,408,985... (The Pell Numbers)

ratio @ infinity
(sqrt (2^2 + 4) + 2)/2 = 1 + sqrt 2
============================

And so on...

To slightly draw the distinction between odd and even y:

EVEN y generate a ratio thusly:
(y/2) + sqrt ((y/2)^2 + 1)

y = 0; 0 + sqrt 1
y = 2; 1 + sqrt 2
y = 4; 2 + sqrt 5
y = 6; 3 + sqrt 10
y = 8; 4 + sqrt 17
y = 10; 5 + sqrt 26
etc.

ODD y generate a ratio thusly:
(sqrt (y^2 + 4) + y)/2

y = 1; (sqrt 5 + 1)/2 (= phi^1)
y = 3; (sqrt 13 + 3)/2
y = 5; (sqrt 29 + 5)/2
y = 7; (sqrt 53 + 7)/2
y = 9; (sqrt 85 + 9)/2
y = 11; (sqrt 125 + 11)/2 (= phi^5)
etc.

How would one go about actually proving this relationship always holds?

TIA

Best,
Raphie
SteveA2
I've actually been messing with some functions like these trying to find a way to describe all possible irrational numbers in a single form, though I've been using a more generalized version of this: a(t)=c(0)*a(t-1)+c(1)*a(t-2)+...+c(n)*(t-n-1)

In the above case we can prove this convergence at least for constrained values of y by fractally unfolding a single iteration (there's a correlation with looking backwards in time also):

A_(n-1) + y*A_(n) = A_(n+1)

Notice that if A remained constant, then the A(n-1) and A(n) terms would be equal and we could call this 'a' and the computation on the left would be a+y*a, which would generate (1+y)*a.

So A(n+1) would have a gain of y+1 over A(n), if all As were constant.

But this gain "forwards in time" is similarly an attentuation "backwards in time" and A(n-1) would be scaled by 1/(y+1) relative to A(n), and if we assumed this approximation true then we'd have A(n-1)=A(n)/(y+1):

Notice that A(n-1) and A(n+1) are two time units apart though and so they aren't in identical terms in time. If we want to find a single exponential scaling per time unit, then this exponent is squared over two time units:

In the end we want a relationship like this, for an exponential scaling of x each time unit:

A(n-1)*x^2~=A(n+1)
A(n-0)*x^1~=A(n+1)
A(n+1)*x^0=A(n+1)

Or alternately an x that solves:

x~=A(n)/A(n-1)~=A(n+1)/A(n)~=...~=A(n+m+1)/A(n+m)~=...

If we simply assign these to be identities, we get:

x=A(n)/A(n-1)
x=A(n+1)/A(n)=(y*A(n)+A(n-1))/A(n)=(y*A(n)+A(n)/x)/A(n)
x=((y+1/x)*A(n))/A(n)
x=(y+1/x)
x-1/x=y
x^2-1=xy
x^2-yx-1=0

We can then use the quadratic formula to solve for this:

x = (y +/- sqrt(y^2 - 4*1-1)) / (2-1)
x = (y +/- sqrt(y^2 + 4)) / 2

So you have two possible solutions (also notice that for y<-2, you have potential problems as well in that you get an exponential oscillation).
Raphie Frank
Speaking of oscillations. For the following formula:

(sqrt (y^2 + 4) + y)/2

Where y = an odd-indexed Lucas Number...

(sqrt (L_1^2 + 4) + L_1)/2 = (sqrt (1^2 + 4) + 1)/2 = 1.61803399 = phi^1
(sqrt (L_3^2 + 4) + L_3)/2 = (sqrt (4^2 + 4) + 4)/2 = 4.23606798 = phi^3
(sqrt (L_5^2 + 4) + L_5)/2 = (sqrt (11^2 + 4) + 11)/2 = 11.0901699 = phi^5
(sqrt (L_7^2 + 4) + L_7)/2 = (sqrt (29^2 + 4) + 29)/2 = 29.0344419 = phi^7
(sqrt (L_9^2 + 4) + L_9)/2 = (sqrt (76^2 + 4) + 76)/2 = 76.0131556 = phi^9

And so on...

I actually just noticed this.

Best,
Raphie
rpenner
The recurrence relation

A(n+2) = y A(n+1) + z A(n) , for z ≠ 0
has a typical solution
A(n) = a b^n + c d^n

Such that
a b^(n+2) + c d^(n+2) = ya b^(n+1) + yc d^(n+1) + za b^(n) + zc d^(n)
which will be true if
a b^2 + c d^2 - ya b - yc d - za - zc = 0
which will be true if
b^2 - y b - z = 0 AND d^2 - y d - z = 0
But this is the same quadratic formula, so b and d have to be the two roots of
x^2 - y x - z = 0 which are x = (y±√(y^2+4z))/2
For concreteness we will have b = (y+√(y^2+4z))/2 and d = (y−√(y^2+4z))/2

Then you solve the inital conditions for
A(1) = a b + c d
A(2) = a b^2 + c d^2

which gives us
a = ( A(2) − d A(1) ) / ( b (b − d) ) [ for b ≠ d ]
c = ( b A(2) − A(1) ) / ( d (b − d) ) [ for b ≠ d ]

So what is the limit of the ratio of A(n+1)/A(n) as n gets large?

If a ≠ 0 and y^2+4z > 0 , then the answer is b, because b^n grows faster than d^n because b > d.

BUT, if a = 0 and c ≠ 0 and y^2+4z > 0, then the answer is d. (The easiest way to fix a = 0 is for A(2) = d and A(1) = 1).

Example:
y = 0, z = 1, A(1) = 1 , A(2) = -1 -- the limit of the ratio is now -1, not 1 as in the "unity series" above.
y = 1, z=1, A(1) = 2, A(2) = 1−√5 -- now the limit of the ratio is (1−√5)/2 not (1+√5)/2
y = 2, z = 1, A(1) = 1, A(2) = 1−√2 -- now the limit of the ratio is (2−√8)/2 not (2+√8)/2

AND, if a = 0 and c = 0, it's a non-starter, 0/0 all the way.

Now if y^2+4z < 0 then the ratio does not converge unless A(1) and A(2) are chosen to make a or c = 0. That's because b and d are now complex numbers of equal magnitude, and the behavior is both oscillating and exponential.

And if y^2+4z = 0 then b = d -- which means what? I have to go out now, but I hope this has been food for thought.
Raphie Frank
QUOTE (Raphie Frank+Feb 7 2009, 06:17 PM)
============================

For y = 2
A_(n-1) + 2*A_(n) = A_(n+1)
-->
1,1,2,5,12,29,70,169,408,985... (The Pell Numbers)

ratio @ infinity
(sqrt (2^2 + 4) + 2)/2 = 1 + sqrt 2
============================

First of all, thank you RPenner. Yes, much food for thought. You too SteveA2. Interesting perspective.

Secondly, in the interests of accuracy, if applying the rule:

A_(n-1) + 2*A_(n) = A_(n+1)

with a [1, 1] starting point, the sequence generated is the Pell-Lucas Sequence, not the Pell Numbers.

[1, 1] 3, 7, 17, 41, 99, 239, 577, 1393...

... the ratio at infinity of which is also 1 + sqrt 2

In similar manner to the way in which the summation of the "Unity" Series (all 1's) generates counting numbers, the summation of the Pell-Lucas Sequence generates Pell Numbers.

Best,
Raphie
SteveA2
QUOTE (Raphie Frank+Feb 7 2009, 08:28 PM)
Speaking of oscillations. For the following formula:

(sqrt (y^2 + 4) + y)/2

Where y = an odd-indexed Lucas Number...

(sqrt (L_1^2 + 4) + L_1)/2 = (sqrt (1^2 + 4) + 1)/2 = 1.61803399 = phi^1
(sqrt (L_3^2 + 4) + L_3)/2 = (sqrt (4^2 + 4) + 4)/2 = 4.23606798 = phi^3
(sqrt (L_5^2 + 4) + L_5)/2 = (sqrt (11^2 + 4) + 11)/2 = 11.0901699 = phi^5
(sqrt (L_7^2 + 4) + L_7)/2 = (sqrt (29^2 + 4) + 29)/2 = 29.0344419 = phi^7
(sqrt (L_9^2 + 4) + L_9)/2 = (sqrt (76^2 + 4) + 76)/2 = 76.0131556 = phi^9

And so on...

I actually just noticed this.

Best,
Raphie

As a quick note, recognize that powers of phi are constructed by an integer coefficient and a coefficient for sqrt(5):

phi^1=(1+sqrt(5))/2
phi^2=(1+sqrt(5))/2*(1+sqrt(5))/2=(1+2*sqrt(5)+sqrt(5)*sqrt(5))/4=(1+5+2*sqrt(5))/4=(3+sqrt(5))/2
phi^3=phi^2*phi^1=(3+sqrt(5))*(1+sqrt(5))/2=(3+4*sqrt(5)+5)/4=2+sqrt(5)
...
phi^n=a+b*sqrt(5)

You could create similar sequences for values other than 5 and generalize each into their own series a+b*sqrt©.

In your case you have a term sqrt(n^2+1) with values of n^2+1 that are multiples of 5 and a square term, 1^2+4=5*1^2, 4^2+4=5*2^2, 11^2+4=5*5^2,29^2+4=5*13^2,76^2=5*34^2 so you'll have an odd power of 5 in the result and get a result of n*sqrt(5), which immediately suggests a possible solution in terms of a power of phi + a possible integer remainder. I'll skip deriving the specific proof in your case because there are some iteresting generalizations to sequences of these forms.

Notice also that the square root terms cancel after 2 units of time, but we can generlize this to other fractional powers, or roots and generate sequences:

a+b*c^(1/d)+e*c^(2/d)+...+f*c^((d-1)/d)

If we have d=6 (if we were working with 1/6th roots, then we can factor these into square roots and cube roots as well and interleave object with 2 and 3 cycle wavefunctions into a single dimension and by making d a product of various powers of primes we can construct arbtrarily complex evolutions of exponential functions over time.

This closely matches physical phenomenon as well as these functions have equivalent spectral features over time and they'll resonate and store or release energy as well as having discrete properties similar to atomic traits etc. It gets as complex as you want (and then there's still more beyond that ... biggrin.gif)

Here's something you might like to look at if you're interested in recursive (and non recursive) filtering structures:

http://www.music.mcgill.ca/~gary/307/week2/filters.html
AlphaNumeric
QUOTE (SteveA2+Feb 7 2009, 08:17 PM)
I've actually been messing with some functions like these trying to find a way to describe all possible irrational numbers in a single form,

Despite not knowing or bothering to find out information on things like convergence and compactness.
QUOTE (SteveA2+Feb 7 2009, 08:17 PM)
In the above case we can prove this convergence at least for constrained values of y by fractally unfolding a single iteration (there's a correlation with looking backwards in time also):
Despite you not knowing what convergence means and showing a misunderstanding of the word 'fractal'.
Raphie Frank
To noone in particular,

As an undergraduate major in Psychology I always felt a bit as if I were "cheating." I didn't feel as if I were learning anything new, but, rather, simply learning names for that which I already was quite familiar with. I felt so bad about the situation I actually added a second major, Dramatic Writing.

Years later, I now actually quite see the value of having been able to define that which I already knew, as it provided a sound framework, later on, upon which to build more complex ideas.

All the same, I would look askance at anyone, then and now, who might ever suggest that I did not understand at the time the "Bell Curve" or the "Just World Hypothesis" or "Confirmation Bias" simply because I had not studied them in a formal manner and could not describe them using words that were accepted by others as conveying "knowledge."

A dime would get the general "You" a dollar that 90% of "average folk" out there understand the notion of "convergence" in a manner that would at least approximate the mathematical sense of the term, and I would equally lay out another dime to a dollar that 90% of those same "average folk" have never even heard of the word "asymptotic."

Just saying...

To noone in particular, of course.

Best,
Raphie
bm1957
QUOTE (Raphie Frank+Feb 10 2009, 04:56 AM)
To noone in particular,

As an undergraduate major in Psychology I always felt a bit as if I were "cheating." I didn't feel as if I were learning anything new, but, rather, simply learning names for that which I already was quite familiar with. I felt so bad about the situation I actually added a second major, Dramatic Writing.

Years later, I now actually quite see the value of having been able to define that which I already knew, as it provided a sound framework, later on, upon which to build more complex ideas.

All the same, I would look askance at anyone, then and now, who might ever suggest that I did not understand at the time the "Bell Curve" or the "Just World Hypothesis" or "Confirmation Bias" simply because I had not studied them in a formal manner and could not describe them using words that were accepted by others as conveying "knowledge."

A dime would get the general "You" a dollar that 90% of "average folk" out there understand the notion of "convergence" in a manner that would at least approximate the mathematical sense of the term, and I would equally lay out another dime to a dollar that 90% of those same "average folk" have never even heard of the word "asymptotic."

Just saying...

To noone in particular, of course.

Best,
Raphie

"Standing on the shoulders of giants"

A fair observation, but it fails to address an important implication.

Convergence, asymptotic, comfirmation bias... all seem quite trivial to me now, but only because I formally learnt the pre-cursors. Like wise, anything which relies on understanding of these concepts would be beyond me if I only had a vague notion of these things which I couldn't communicate.

So, maybe you did understand the "Bell Curve" or the "Just World Hypothesis" or "Confirmation Bias" informally, but a dime to a dollar you didn't even have a vague concept of anything they build upon; and if you did have an appreciation of them, this is only because you had the advantages of a formal education which must have been almost to that level.

Try to tease an understanding of 'convergence' from someone with no formal training in math and I believe you will struggle. In fact, try to tease an understanding of mulitplication out of someone who doesn't have the tools to talk to you about addition and I believe you'll have the same problem.

So if (and only if) you are trying to make the implication that you believe you have an inate ability to comprehend advanced mathematical concepts without the background formal 'knowledge', I would have to disagree and propose that in fact it is blissful ignorance of the pre-requisites that would allow such farcical ponderings.

Just my opinion, of course.
SteveA2
To noone in particular, consider that even a child moving their hand is performing matrix multiplication or solving simultaineous differential equations and someone hearing a sound is performing the equivalent of a fourier transform (actually something better) and statistical pattern recognition using hidden markov models and that someone seeing is performing various 2 dimensional gaussian transformations, contour detection and feature mapping with triangulation between stereoscopic images etc.

I've done some laser light shows and have found that people intuitively understand advanced mathematical concepts - they see the beauty in mathematical forms and can emulate or predict its forms in nature. In fact there are very likely mathematical functions that people already intuitively recognize and can predict the features of that modern mathematics does not yet have a grasp of.

Of course it's great when we can do this more precisely and refine something from a coarser probability into an exact representation of the "kernel" in mathematics, but there are things that people can do quite easily that we haven't been able to even get a super computer to do.
bm1957
QUOTE (SteveA2+Feb 10 2009, 04:39 PM)
To noone in particular, consider that even a child moving their hand is performing matrix multiplication or solving simultaineous differential equations and someone hearing a sound is performing the equivalent of a fourier transform (actually something better) and statistical pattern recognition using hidden markov models and that someone seeing is performing various 2 dimensional gaussian transformations, contour detection and feature mapping with triangulation between stereoscopic images etc.

I've done some laser light shows and have found that people intuitively understand advanced mathematical concepts - they see the beauty in mathematical forms and can emulate or predict its forms in nature. In fact there are very likely mathematical functions that people already intuitively recognize and can predict the features of that modern mathematics does not yet have a grasp of.

Of course it's great when we can do this more precisely and refine something from a coarser probability into an exact representation of the "kernel" in mathematics, but there are things that people can do quite easily that we haven't been able to even get a super computer to do.

Complete and utter bullocks
rpenner
I concur.
Raphie Frank
Dear SteveA2,

Here is what Richard Dawkins, evolutionary biologist, had to say on the process of catching a ball in his book, The Selfish Gene (p.96)

=========================================================
"When a man throws a ball high in the air and catches it again he behaves as if he had solved a set of differential equations in predicting the trajectory of the ball. He may neither know nor care what a differential equation is, but this does not affect his skill with the ball. At some subconscious level, something functionally equivalent to the methematical equations is going on."
=========================================================

That said, you should know where I got the quote. It's on page 9 of "Gut Feelings: The Intelligence of the Unconscious" (2007) by Gerd Gigerenzer, Director of the Max Planck Institute for Human Development. He brings up Dawkin's Statement by way of setting up a straw man, so that he can make the case for the Gaze Heuristic which goes counter to Dawkin's view. Here is a bit about the Gaze Heuristic from Wikipedia:

=========================================================
The gaze heuristic is a heuristic employed by people when trying to catch a ball. Experimental studies have shown that people do not act as though they were solving a system of differential equations that describe the forces acting on the ball while it is in the air and then run to the place at which the ball is predicted to hit the ground. Instead they fixate the ball with their eyes and move so as to keep the angle of the gaze either constant or within a certain range. Moving in such a fashion assures that the ball will hit the catcher.[1][2]
http://en.wikipedia.org/wiki/Gaze_heuristic
=========================================================

Although I appreciate Gigerenzer's point, the issues that matter for me (aside from the fundamentally four-dimensional approach implied by the Gaze Heuristic) are two-fold. Firstly, the end result. The ball gets caught, and it gets caught, by and large, in a very effective manner. Secondly, a specific outcome is achieved in a far more economical manner than if one was "performing math on the fly." In other words, one outcome, at least two different ways there.

Speaking for myself, I am far more interested in the other ways there than I am in the ways we already know about.

Best,
Raphie

P.S. The ratio between successive numbers in the progression for -1*A_(n_1) + y*A_(n)= A_(n+1) as n approaches infinity would seem to be (y + sqrt (y^2 - 4))/2 for all y not equal to -1 or 0. If you run the numbers, you'll notice that this generates the even powers of phi where y = L_2n. Best, RF
Granouille
Do you think we throw the ball with the same principles in mind? Like leading a target?
SteveA2
QUOTE (Raphie Frank+Feb 12 2009, 01:11 AM)
Dear SteveA2,

Here is what Richard Dawkins, evolutionary biologist, had to say on the prcess of catching a ball in his 1976 book, The Selfish Gene (p.96)

=========================================================
"When a man throws a ball high in the air and catches it again he behaves as if he had solved a set of differential equations in predicting the trajectory of the ball. He may neither know nor care what a differential equation is, but this does not affect his skill with the ball. At some subconscious level, something functionally equivalent to the methematical equations is going on."
=========================================================

That said, you should know where I got the quote. It's on page 9 of "Gut Feelings: The Intelligence of the Unconscious" (2007) by Gerd Gigerenzer, Director of the Max Planck Institute for Human Development. He brings up Dawkin's Statement by way of setting up a straw man, so that he can make the case for the Gaze Heuristic which goes counter to Dawkin's view. Here is a bit about the Gaze Heuristic from Wikipedia:

=========================================================
The gaze heuristic is a heuristic employed by people when trying to catch a ball. Experimental studies have shown that people do not act as though they were solving a system of differential equations that describe the forces acting on the ball while it is in the air and then run to the place at which the ball is predicted to hit the ground. Instead they fixate the ball with their eyes and move so as to keep the angle of the gaze either constant or within a certain range. Moving in such a fashion assures that the ball will hit the catcher.[1][2]
http://en.wikipedia.org/wiki/Gaze_heuristic
=========================================================

Although I appreciate Gigerenzer's point, the issues that matter for me (aside from the fundamentally four-dimensional approach implied by the Gaze Heuristic) are two-fold. Firstly, the end result. The ball gets caught, and it gets caught, by and large, in a very effective manner. Secondly, a specific outcome is achieved in a far more economical manner than if one was "performing math on the fly." In other words, one outcome, at least two different ways there.

Speaking for myself, I am far more interested in the other ways there than I am in the ways we already know about.

Best,
Raphie

P.S. The ratio between successive numbers in the progression for -1*A_(n_1) + y*A_(n) as n approaches infinity would seem to be (n + sqrt (n^2 - 4))/2 for all y not equal to -1 or 0. If you run the numbers, you'll notice that this generates the even powers of phi where y = L_2n. Best, RF

Also, even in that scenario of maintaining such a constant angle, you'd still be required to compensate for inertia and "lead" the motion of the ball in terms of your acceleration, because you can't move at a velocity without first accelerating and the same would occur for stopping after catching the ball. You need to construct a leading term and begin to slow before stopping.

There's a very common controller used in mathematics that emulates much of this, though necessarily quite as robustly as a human, except that mechanical precision and reaction times can be better (which gives this not an intellectual advantage over a human, but a greater response frequency and less delay).

Proportional, Integral and Differential Controller:
http://en.wikipedia.org/wiki/PID_controller

People intuitively understand this subject and this is how people have learned mathematics from analyzing the characteristics of their subconscious and physical actions.

Or as another example, balancing a broomstick on a finger is quite a complex task to program. It took quite a bit of work in artificial intelligence to develop algorithms capable of this (and we haven't even come to some of the "basic" transformations employed by the optic nerves yet much less higher level functions such as recognition of music structure or recognizing timbers in a sound or voice etc.)

The body does this and things we likely don't even understand yet and this shouldn't be particularly surprising either when we recognize that everything humanity knows of the universe could be nothing more complex that the complexities that the body can convey to the mind.

A good musician can be thankful that others are able to understand the music and appreciate the content. An appreciation of these subjects arises from innate abilities.

Thanks for your post, Raphie.
PhysOrg scientific forums are totally dedicated to science, physics, and technology. Besides topical forums such as nanotechnology, quantum physics, silicon and III-V technology, applied physics, materials, space and others, you can also join our news and publications discussions. We also provide an off-topic forum category. If you need specific help on a scientific problem or have a question related to physics or technology, visit the PhysOrg Forums. Here you’ll find experts from various fields online every day.
To quit out of "lo-fi" mode and return to the regular forums, please click here.