Condition for a number to be a Fibonacci one

  • Thread starter muzialis
  • Start date
  • Tags
    Condition
In summary, the statement on a magazine page discusses the relationship between Fibonacci numbers and perfect squares. If a number is a Fibonacci number, then one of two conditions involving the number and the golden ratio must be true. The explanation for this can be found in the Binet formula and the properties of the golden ratio. The Wikipedia article on Fibonacci numbers also addresses this relationship, but may not provide a clear explanation.
  • #1
muzialis
166
1
Hi all, I found the following statement on a magazine page and cannot understand it. It is possibly very distant from the little maths I know, but made me very curious.
It is therein said that if a number $$n$$ is a Fibonacci number, then one of the conditions $$ 5n^2 + 4$$ or $$5n^2-4$$ is true.
The conclusion follows from the following relationship, where $$A_n$$ is the n-th number in the Fibonacci sequence.
$$n = log_{golden ratio} \frac{A_n \sqrt{5} + \sqrt{5A_n^2 +-4}}{2}$$.
I am unable to see how the conclusion is drawn, any hint would be most appreciated.
Thanks a lot
 
Physics news on Phys.org
  • #2
muzialis said:
one of the conditions $$ 5n^2 + 4$$ or $$5n^2-4$$ is true.

These are not conditions, these are expressions.
 
  • #3
Borek,

how to disagree with you...I of course forgot to mention the fact those expression have to be perfect squares, i.e. the square of an integer number.

thanks
 
  • #4
So you disagree with Borek while admitting that he was right?
 
  • #5
Hallsoflvy,

regreftully I do not understand what you mean.
Borek's remark was of course correct and I agree with it, as clearly stated in my post. Subsequently I tried to add the (missing) information that would make the problem at least meaningful. i.e. I clarified those "expressions" have to be perfectsquares, leading to conditions.
 
  • #6
The Binet formula gives a closed form solution for finding the nth Fibonacci number:
[tex]F_n = \frac{\phi^n - (-1/\phi)^{-n}}{\sqrt 5}[/tex]or
[tex]F_n =\begin{cases}
\frac{\phi^n - (\phi)^{-n}}{\sqrt 5} & \text{$n$ even} \\
\frac{\phi^n + (\phi)^{-n}}{\sqrt 5} & \text{$n$ odd}
\end{cases}[/tex]
Solving for ##\phi^n## yields
[tex]\phi^n =\begin{cases}
\frac{F_n\sqrt 5 + \sqrt{5F_n^2 + 4}} 2 & \text{$n$ even} \\
\frac{F_n\sqrt 5 + \sqrt{5F_n^2 - 4}} 2 & \text{$n$ odd}
\end{cases}[/tex]
Taking the log of both sides to base ##\phi## gives an closed form solution for finding the index number given a Fibonacci number.

Note that ##\phi^n## can be expressed in the form ##\phi^n = \frac {a_n + b_n\sqrt 5} 2## where ##a_n## and ##b_n## are integers. To match that form, at least one of ##\sqrt{5F_n^2 \pm 4}## must be an integer. In other words, at least one of ##5F_n^2 \pm 4## must be a perfect square.
 
  • Like
Likes 1 person
  • #7
The wikipedia article on Fibonacci number answers your question. Algebra alone, from the definition of log, does not suffice.
 
  • #10
DH, thanks a lot for your help.
I checked Wikipedia too and was still not getting it...your explanation involving Binet's formula and the representation of the golden ratio is clear now, bit out of sheer curiosity what is that is being said on Wikipedia about the logarithms, integers, irrationals...? How does the wikipedia article explains the conditions?
 
  • #11
muzialis said:
DH, thanks a lot for your help.
I checked Wikipedia too and was still not getting it...your explanation involving Binet's formula and the representation of the golden ratio is clear now, bit out of sheer curiosity what is that is being said on Wikipedia about the logarithms, integers, irrationals...? How does the wikipedia article explains the conditions?

My interpretation of what wiki says is as follow:

Since 5 n2+/-4 cannot be a multiple of 5, if it is not a perfect square, its square root is not a multiple of √5. To me, from the prior discussion, this made it obvious that the log of the operand would then be irrational, as indicated, (while it must be an integer for a Fibonacci number). DH's argument is much clearer. Basically, the wiki article expected you to do a lot of what DH wrote out, from the various formulas given.
 
Last edited:
  • #12
muzialis said:
DH, thanks a lot for your help.
I checked Wikipedia too and was still not getting it...your explanation involving Binet's formula and the representation of the golden ratio is clear now, bit out of sheer curiosity what is that is being said on Wikipedia about the logarithms, integers, irrationals...? How does the wikipedia article explains the conditions?
That's wikipedia for ya. Any given wikipedia usually is correct (but do beware; sometimes it isn't), but the quality of the writing oftentimes is subpar.

The reason this works is that ##\phi^n## for non-negative integers ##n## can be expressed as ##\phi^n = \frac {a_n+b_n\sqrt 5} 2## where ##a_n## and ##b_n## are integers. I'll leave the proof of that up to you. The Binet formula can be rewritten as ##\phi^n = \frac{\sqrt{5F_n^2\pm 4} + F_n\sqrt 5} 2##. I'll also leave the derivation of that up to you. Equating these two expressions for ##\phi^n## means that ##\sqrt{5F_n^2\pm 4}## must be of the form ##c_n+d_n\sqrt 5##. Squaring this yields ##c_n^2+5d_n^2 + 2c_nd_n\sqrt 5##, and this must be an integer (##5F_n^2\pm 4## is an integer). This in turn means that at least one of ##c_n## or ##d_n## must be zero. ##c_n=0## doesn't work because the ##a_n## are positive for all n≥ 0. That means ##d_n## must be zero, which means ##5F_n^2\pm 4## is a perfect square.
 
  • Like
Likes 1 person
  • #13
Very usefuland interesting, many thanks to all.
 
  • #14
Looks like something that can be proven by induction.
 
  • #15
PAllen said:
I agree it could say more.
That to me is the basic problem with wikipedia articles. If I already know the subject area quite well, a wiki article can be a great aid as a reminder. I can also tell whether the article of interest is just wrong (which does happen) or poorly written (which happens a lot). If I am somewhat familiar with the subject area, a wiki article can sometimes be of aid (but sometimes not). However, lack of familiarity might mean I'm led astray by an erroneous or poorly written article. The worse case is when I am at best marginally familiar with the subject area. There, those wiki articles are often atrocious. I don't know if I'm looking at crackpot nonsense that will soon be reverted, and the writing is oftentimes so bad that I can't make heads or tails of the article.

Borek said:
Looks like something that can be proven by induction.
Yes, it can. The issue is to prove that ##\phi^n = \frac{a_n + b_n \sqrt 5} 2## where ##a_n## and ##b_n## are integers, and in the process find meaningful expressions for those ##a_n## and ##b_n##. Since ##\phi = \frac {1 +\sqrt 5} 2##, this conjecture is obviously true for n=1, with ##a_1 = b_1 =1##. We have a basis point for the induction. As a sanity check, what about ##\phi^0 =1##? This obviously works to, with ##a_0 = 2## and ##b_0 = 0##.

Assuming ##\phi^n = \frac{a_n + b_n \sqrt 5} 2##, multiplying by ##\phi## yields ##\phi^{n+1} = \frac {an+5b_n + (an+b_n) \sqrt 5} 4##. Reading off the values for ##a_{n+1}## and ##b_{n+1}## yields ##a_{n+1} = \frac{a_n+5b_n}2## and ##b_{n+1} = frac {a_n + b_n}2##. Not quite home yet: What if ##a_n+b_n## is odd?

The expression for ##a_{n+1}## can be written in terms of ##b_{n+1}##, yielding ##a_{n+1} = b_{n+1}+2b_n##, from whence ##a_n = b_n + 2b_{n-1}##. Putting this back into the expression for ##b_{n+1}## yields ##b_{n+1} = b_n+b_{n-1}##. Since ##b_0=0## and ##b_1=1##, this means that bn is just the nth Fibonacci number.

What about ##a_n##? From the above, we have ##a_n = F_n + 2F_{n-1}##. Squaring this yields ##a_n^2 = F_n^2 + 4F_nF_{n-1} + 4F_{n-1}^2##, and with a little manipulation this becomes ##a_n^2 = F_n^2 + 4F_{n-1}F_{n+1}##. Via Cassini's identity, ##F_{n-1}F_{n+1} = F_n^2 + (-1)^n##, and thus
[tex]a_n = \begin{cases}
5F_n^2 + 4 & \text{$n$ even} \\
5F_n^2 - 4 & \text{$n$ odd}
\end{cases}[/tex]
In summary,
[tex]
\phi^n = \frac {F_n\sqrt 5 + \sqrt{5F_n^2 \pm 4}} /2
[/tex] where +4 is used when n is even, -4 when n is odd.
 

1. What is the condition for a number to be a Fibonacci one?

The condition for a number to be a Fibonacci one is that it must be the sum of the two preceding numbers in the Fibonacci sequence. The sequence starts with 0 and 1, so each number after that is the sum of the previous two numbers.

2. Can any number be a Fibonacci one?

No, not every number can be a Fibonacci one. Only numbers that meet the condition of being the sum of the two preceding numbers in the sequence are considered Fibonacci numbers.

3. Is there a limit to how high a Fibonacci number can be?

There is no theoretical limit to how high a Fibonacci number can be, but as the numbers get larger, they become more difficult to calculate and have less significance in relation to the previous numbers in the sequence.

4. Why are Fibonacci numbers significant?

Fibonacci numbers are significant because they appear in many natural patterns and phenomena, such as the branching of trees, the spirals of seashells, and the arrangement of seeds in a sunflower. They also have important applications in mathematics and computer science.

5. Can a negative number be a Fibonacci one?

No, by convention, Fibonacci numbers are only considered to be positive integers. However, there is a related sequence called the "negative Fibonacci sequence" where the numbers are the negative counterparts of the original Fibonacci sequence.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
4
Views
3K
  • Atomic and Condensed Matter
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
1K
Replies
1
Views
1K
  • General Math
Replies
1
Views
1K
  • Differential Equations
Replies
1
Views
707
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
5K
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
Back
Top