Can You Solve This Intense Fibonacci Challenge?

  • Thread starter steven187
  • Start date
In summary, the conversation discussed a problem involving the Fibonacci sequence and its convergence to the golden ratio. The participants offered different methods for solving the problem, including using difference equations and the partial fraction expansion of (1 + √5)/2. They also discussed the importance of understanding the basics of analysis and using initial conditions to find a particular solution.
  • #1
steven187
176
0
Warning:Danger Zone II

hello all

Check this out I have been working on this over the last few days, its pretty intense, I don't think I am getting anywhere, anyway peoples good luck

prove
[tex]\lim_{n\longrightarrow\infty}\frac{F_n}{F_{n-1}}=\frac{1+\sqrt{5}}{2}[/tex]
where
[tex]F_n=F_{n-1}+F_{n-2} \ \forall n>2[/tex]
A Fibonacci sequence
 
Physics news on Phys.org
  • #2
Let G_n be F_n/F_{n-1} find an equation the G_n satisfy (this is easy and is obtainable from the step you've written. (hit the limit is the golden ratio, the root of x^2-x-1))

1. assume G_n converges, to G, find G from the equaiton you just made (hint take limits in both sides)

2. now show that G_n is indeed convergent (several ways of showing this kind of thing, say if x_n is an increasing (resp. decreasing) sequnec bounded above (resp. below) it converges. you may find the arithmetic-geometric mean (or some other inequality) helpful.)

please acn i ask others to refrain from posting *solutions*, though if my hints are off please correct them. i haven't checked them, but this *must* be how one solves it since it is the only method available to us. it's probably the worng time of year to be homework but it does feel like we solving all of steven's examples for him. by now the answers hould be startng to come moer easily to you, steven. this sounds harsher than i mean to be typing it, sorry if it osunds that way. you may way have been working on this for ages.

when you've seen the idea once, though, it becomes clear what to do in all cases like this.
 
Last edited:
  • #3
:smile: This is a fairly standard problem, I must have come across it at least a few times in my courses. There are atleast a couple of ways of doing this (I seem to remember a much more 'exoitic' way of doing it), but matt grime's is the most obvious way of thinking about it.

Although, something worth noting is that you have not defined F0 and F1.
 
  • #4
May I offer another route of inquiry:

The Fibonacci relation above is in the form of a "second-order difference equation". Difference equations can be solved very much like linear differential equations: You determine the auxiliary equation, solve for the roots, form the complimentary function from the roots and then determine the constants c1 and c2 using the the initial conditions (f(0) and f(1)) to obtain the specific solution. Once the specific solution is obtained this way, the limit of the above ratio can be determined. :smile:

Edit: I made a mistake. :blushing: I haven't figured out how to determine the limit from the equation derived from the difference equation. I'll work on it some more.

Edit2: You know what, this is Calculus/Analysis and I think my route is more, well difference equations and not Analysis. So nevermind. Also, I was able to prove the limit via this route.
 
Last edited:
  • #5
Let's say you could come up with a formula
[tex] f_n = c_1 r_1^n + c_2 r_2^n [/tex]
and you could prove that [itex]r1 > r2 >0 [/itex].

Then you could write
[tex] \frac{f_{n+1}}{f_n} = \frac{ c_1 r_1^{n+1} + c_2 r_2^{n+1} }{
c_1 r_1^n + c_2 r_2^n} \\
= \frac {r_1 + \frac{c_2 r_2}{c_1} \left( \frac{r_2}{r_1} \right)^n}
{1 + \frac{c_2}{c_1} \left( \frac{r_2}{r_1} \right)^n }
[/tex]

Then in the n -> infinity limit, [itex] (r2/r1)^n \rightarrow 0 [/itex].

Then you could say:
[tex] \lim_{n \rightarrow \infty} \frac{f_{n+1}}{f_n} = r_1[/tex]

--
 
  • #6
yeah, or you could just use the axiom of convergence and that the square of a real number is positive which is all I did. still two methods are better than one i suppose, but the "general" method is what they're after since it reinforces the basics of analysis, speaking as a teacher of analysis. it's also entirely possible that my general method doesn't work, you know.
 
Last edited:
  • #7
qbert said:
Let's say you could come up with a formula
[tex] f_n = c_1 r_1^n + c_2 r_2^n [/tex]
and you could prove that [itex]r1 > r2 >0 [/itex].

Then you could write
[tex] \frac{f_{n+1}}{f_n} = \frac{ c_1 r_1^{n+1} + c_2 r_2^{n+1} }{
c_1 r_1^n + c_2 r_2^n} \\
= \frac {r_1 + \frac{c_2 r_2}{c_1} \left( \frac{r_2}{r_1} \right)^n}
{1 + \frac{c_2}{c_1} \left( \frac{r_2}{r_1} \right)^n }
[/tex]

Then in the n -> infinity limit, [itex] (r2/r1)^n \rightarrow 0 [/itex].

Then you could say:
[tex] \lim_{n \rightarrow \infty} \frac{f_{n+1}}{f_n} = r_1[/tex]

--

Very nice Qbert. That is in fact the route taken via difference equations as your first is a solution to the equation:

[tex]y_{n+2}+a_1y_{n+1}+a_0y_n=0[/tex]

Although I approached the limit in a more messy direction but obtained the same result.
 
  • #8
looking at the first few terms of the ratios F_n/F_{n-1} then the sequence alternates between greater than the limit and less than the limit (1,2,1.5,1.66...,1.6,...) so for my allegedly better general method you're actually goingt o have some worl to do if it even is possible that way. (i think i can by soem tricks show that the sequence is cauchy, if taht'd be of interest)
 
  • #9
The last time I proved this, I did it by showing that the partial fraction expansion of [itex](1 + \sqrt{5})/2[/itex] was equal to Fn/Fn-1 and the rest of the proof was trivial.
 
  • #10
I'd like to explain, for those reading this and perhaps not familiar with solving difference equations, how to solve the Fibonacci equation using them. You'll notice the close resemblance to the method used in solving a linear second-order ODE:

Rewriting the Fibonacci equation as:

[tex]F_n-F_{n-1}-F_{n-2}=0;\quad F_0=1,\quad F_1=1[/tex]

we attempt a trial solution of the form:

[tex]F_n=r^n;\quad r\ne 0[/tex]

Substituting this into the Fibonacci equation we obtain:

[tex]r^n-r^{n-1}-r^{n-2}=0[/tex]

or:

[tex]r^{n-2}(r^2-r-1)=0[/tex]

Thus:

[tex]r^2-r-1=0[/tex]

with:

[tex]r_1=\frac{1+\sqrt{5}}{2}=\phi;\quad r_2=\frac{1-\sqrt{5}}{2}=1-\phi[/tex]

Since the roots are real and distinct, the general solution to this difference equation is given by:

[tex]F_n=c_1\phi^n+c_2(1-\phi)^n[/tex]

Using the initial conditions we obtain:

[tex]1=c_1+c_2[/tex]

[tex]1=c_1\phi+c_2(1-\phi)[/tex]

Solving for [itex]c_1[/itex] and [itex]c_2[/itex] and noting that [itex]2\phi-1=\sqrt{5}[/itex], we obtain as the particular solution:

[tex]F_n=\left(\frac{\phi}{\sqrt{5}}\right)\phi^n+\left(\frac{\phi-1}{\sqrt{5}}\right)(1-\phi)^n[/tex]
 
  • #11
hello all

well that was a nice approach, after playing around with it I ended up doing it like this
let
[tex]\lim_{n\longrightarrow\infty}\frac{F_n}{F_{n-1}}=L[/tex]

then from this
[tex]F_n=F_{n-1}+F_{n-2}[/tex]

we get
[tex]\frac{F_n}{F_{n-1}}= 1 +\frac{F_{n-2}}{F_{n-1}}[/tex]

[tex]\frac{F_n}{F_{n-1}}= 1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}} [/tex]

while considering that the limit is unique and taking the limit of both sides we get
[tex]\lim_{n\longrightarrow\infty} \frac{F_n}{F_{n-1}}=\lim_{n\longrightarrow\infty}1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}}[/tex]

[tex]L=1 +\frac{1}{L}[/tex]

[tex]L^2-L-1=0[/tex]

[tex]L=\frac{1+\sqrt{5}}{2};\frac{1-\sqrt{5}}{2}[/tex]

since
[tex]\frac{F_n}{F_{n-1}}>1 \\ \forall n\epsilon N[/tex]

then
[tex]L=\frac{1+\sqrt{5}}{2}[/tex]

I am currently working on a method that involves linear algebra its pretty intense but hopefully I should get to my destination, once I do il post it up as usual :approve: .
 
  • #12
steven187 said:
hello all

well that was a nice approach, after playing around with it I ended up doing it like this
let
[tex]\lim_{n\longrightarrow\infty}\frac{F_n}{F_{n-1}}=L[/tex]

then from this
[tex]F_n=F_{n-1}+F_{n-2}[/tex]

we get
[tex]\frac{F_n}{F_{n-1}}= 1 +\frac{F_{n-2}}{F_{n-1}}[/tex]

[tex]\frac{F_n}{F_{n-1}}= 1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}} [/tex]

while considering that the limit is unique and taking the limit of both sides we get
[tex]\lim_{n\longrightarrow\infty} \frac{F_n}{F_{n-1}}=\lim_{n\longrightarrow\infty}1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}}[/tex]

[tex]L=1 +\frac{1}{L}[/tex]

[tex]L^2-L-1=0[/tex]

[tex]L=\frac{1+\sqrt{5}}{2};\frac{1-\sqrt{5}}{2}[/tex]

since
[tex]\frac{F_n}{F_{n-1}}>1 \\ \forall n\epsilon N[/tex]

then
[tex]L=\frac{1+\sqrt{5}}{2}[/tex]

I am currently working on a method that involves linear algebra its pretty intense but hopefully I should get to my destination, once I do il post it up as usual :approve: .

Hello Steven.

That's a nice way you did that and I can't see anything wrong but I'm not the Analysis expert (well ok, far from it but I digress). Can you post the outlines of the linear algebra approach?

Thanks,
Salty
 
  • #13
The problem with steven's approach is that it doesn't show that the sequence actually converges...
 
  • #14
Muzza said:
The problem with steven's approach is that it doesn't show that the sequence actually converges...


Ahhhhhh . . . good for you Muzza. I see that now. Thanks. :smile:
 
  • #15
Like I say if you've done anything on continued fraction expansion then just expand [itex](1 + \sqrt{5})/2[/tex] and look at pn and qn. If not then, erm, try something else :uhh:
 
  • #16
hello all

this is my basically my linear algebra approach enjoy, I don't know if anybody knew this but there is a general formulae in matrix form

[tex]A^n=\left(\begin{array}{cc}F_{n+1}&F_n\\F_n&F_{n-1}\end{array}\right)[/tex]
where
[tex]A=\left(\begin{array}{cc}1&1\\1&0\end{array}\right)[/tex]
by solving the characteristics equation
[tex]|A-\lambda I|=0[/tex]
we get
[tex](1-\lambda)(-\lambda)-1=0[/tex]
[tex]\lambda^2-\lambda-1=0[/tex]
as a result the eigenvalues are
[tex]\lambda=\phi;(1-\phi)[/tex]
then by multiplying by [tex]\lambda^n[/tex]
we get
[tex]\lambda^{n+2}-\lambda^{n+1}-\lambda^{n}=0[/tex]
and so
[tex]n\mapsto \phi^n[/tex]
also
[tex]n\mapsto (1-\phi)^n[/tex]
just to note the eigenvectors are linear independent of each other and so the eigenvectors can be put into a linear combination, as a result we can have
[tex]n\mapsto a\phi^n+b(1-\phi)^n[/tex]
to accommodate for all linear combinations and by adjusting the coefficients for the initial values we get
[tex]F_n=\frac{\phi^n+(1-\phi)^n}{\sqrt{5}}[/tex]
now we let
[tex]a=\phi[/tex]
and
[tex]b=1-\phi[/tex]
[tex]a-b=\sqrt{5}[/tex]
then
[tex]F_n=\frac{a^n-b^n}{a-b}[/tex]
then we have
[tex]\frac{F_{n+1}}{F_n}=\frac{a^{n+1}-b^{n+1}}{a^n-b^n}[/tex]
we then take the limit of both sides and we get
[tex]\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}=\lim_{n\rightarrow\infty}\frac{a^{n+1}-b^{n+1}}{a^n-b^n}[/tex]
since
[tex]|b|<1[/tex]
and
[tex]\lim_{n\rightarrow\infty}b^n=0[/tex]
then
[tex]\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}=\lim_{n\rightarrow\infty}\frac{a^{n+1}}{a^n}=a=\phi[/tex]
oh yes about the existence of the limit that aint too hard all i did was show that
[tex]1\le\frac{F_{n+1}}{F_n}\le 2[/tex]
by using the fact
[tex]a_{n+1}=1+\frac{1}{a_n}[/tex]
then i let
[tex]a_n=\frac{F_{n+1}}{F_n}[/tex]
and showed that the subsequence (by mathematical Induction)
[tex]a_{2n+1}[/tex] is increasing and
[tex]a_{2n}[/tex] is decreasing
and so since all terms are positive then both subsequences converge to the same limit :approve:

steven
 
  • #17
...I don't know if anybody knew this...

The same method for working out the closed form of the Fibonacci sequence is detailed in "Basic Linear Algebra" by TS Blyth. ;)

...and so since all terms are positive then both subsequences converge to the same limit

Are you sure that this is sound reasoning? Seems like this sequence would be a counterexample:

a_(2n) = 1/n + 1
a_(2n + 1) = 2 - 1/n
 
  • #18
that first one is a nice method, will have to remember it.

the second one does indeed have problems as muzza mentions but they can be gotten round. i'd be itnerested to see the proofs that the even and odd parts are increasing and devreasing resp.

you cannot conclude that the converge to the same thing, though if one forms a recurrence that the even and odd terms satisfy like you did for the sequence in general then you can take limits in that relation and find the limits and show they are the same.
 
  • #19
hello all

well i wanted to show that
[tex]a_{2n+2}-a_{2n}\le 0[/tex]
[tex]a_{2n+2}-a_{2n}=\frac{a_{2n}-a_{2n-2}}{(1+a_{2n})(1+a_{2n-2})}[/tex]
by considering that
[tex]1\le a_{n} \le 2[/tex]
then
[tex] (1+a_{2n})(1+a_{2n-2})\ge 0[/tex]
infact it should be
[tex]4\le (1+a_{2n})(1+a_{2n-2})\le 9[/tex]
and so
[tex]a_{2n+2}-a_{2n}[/tex]
has the same sign as
[tex]a_{2n}-a_{2n-2}[/tex]
now by considering that
[tex]a_2=2[/tex] and [tex]a_4<a_2[/tex]
then
[tex]a_{2n+2}-a_{2n}< a_{2n}-a_{2n-2}\le a_4-a_2\le 0[/tex]
and this is true for all n by induction and hence
[tex]a_{2n}[/tex] a decreasing sequence
similarly for [tex]a_{2n+1}[/tex]
and as for :

"..and so since all terms are positive then both subsequences converge to the same limit "

so we have 2 subsequences one that is decreasing and bounded by 1 so it must have a limit let us denote it by r also we have a increasing sequence which is bounded above by 2 so it must have a limit let us denote it by t

now since the terms of the sequence satisfy the equation
[tex]a_{n+2}=1+\frac{a_n}{1+a_n}[/tex]
then the limit must also satisfy this equation
[tex]r^2-r-1=0[/tex]
[tex]t^2-t-1=0[/tex]
and since
[tex]a_n> 0 \ \forall n\epsilon N[/tex]
then
[tex]r,t>0[/tex]
and hence the limit is unique
[tex]r=t=\frac{1+\sqrt{5}}{2}[/tex]

steven
 
Last edited:
  • #20
well done, that answer is perfect in all senses.
 

1. What is "Warning Anger Zone II"?

"Warning Anger Zone II" is a term used to describe a state of anger that is approaching or reaching a dangerous level. It is typically characterized by intense emotions, aggressive behavior, and a lack of control.

2. How is "Warning Anger Zone II" different from regular anger?

"Warning Anger Zone II" is different from regular anger in that it is a heightened state of anger that can be dangerous and potentially harmful. It is often accompanied by physical and emotional symptoms such as increased heart rate, sweating, and loss of rational thinking.

3. What are some common triggers for "Warning Anger Zone II"?

Some common triggers for "Warning Anger Zone II" include feeling threatened, experiencing a loss of control, feeling disrespected or humiliated, and being under a high level of stress. However, triggers can vary from person to person.

4. How can someone recognize when they are in "Warning Anger Zone II"?

There are several signs that someone may be in "Warning Anger Zone II" including physical reactions like increased heart rate and muscle tension, cognitive symptoms such as racing thoughts and difficulty concentrating, and behavioral indicators like aggressive outbursts or destructive behavior.

5. What can be done to manage "Warning Anger Zone II"?

If someone finds themselves in "Warning Anger Zone II", it is important to take a step back and try to calm down. This can include deep breathing exercises, counting to ten, or removing oneself from the situation. It is also important to seek help from a mental health professional to learn healthy coping mechanisms and prevent future episodes.

Similar threads

  • Calculus
Replies
3
Views
1K
Replies
1
Views
922
Replies
0
Views
288
Replies
41
Views
2K
  • General Math
Replies
7
Views
2K
  • Topology and Analysis
Replies
21
Views
1K
  • Topology and Analysis
Replies
4
Views
2K
  • Topology and Analysis
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
3K
  • Calculus and Beyond Homework Help
Replies
8
Views
767
Back
Top