Condition for a number to be a Fibonacci one

[muzialis]

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

 

[Borek]

one of the conditions $$ 5n^2 + 4$$ or $$5n^2-4$$ is true.

These are not conditions, these are expressions.

 

[muzialis]

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

 

[HallsofIvy]

So you disagree with Borek while admitting that he was right?

 

[muzialis]

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.

 

[D H]

The Binet formula gives a closed form solution for finding the n^th Fibonacci number:
F_n = \frac{\phi^n - (-1/\phi)^{-n}}{\sqrt 5}or
F_n =\begin{cases}<br /> \frac{\phi^n - (\phi)^{-n}}{\sqrt 5} &amp; \text{$n$ even} \\<br /> \frac{\phi^n + (\phi)^{-n}}{\sqrt 5} &amp; \text{$n$ odd}<br /> \end{cases}
Solving for $\phi^n$ yields
\phi^n =\begin{cases}<br /> \frac{F_n\sqrt 5 + \sqrt{5F_n^2 + 4}} 2 &amp; \text{$n$ even} \\<br /> \frac{F_n\sqrt 5 + \sqrt{5F_n^2 - 4}} 2 &amp; \text{$n$ odd}<br /> \end{cases}
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.

 

[PAllen]

The wikipedia article on Fibonacci number answers your question. Algebra alone, from the definition of log, does not suffice.

 

[D H]

The wikipedia article on Fibonacci number answers your question.

I disagree. The wiki article states the condition $5F_n^2 \pm 4$ must be a perfect square, but it doesn't do justice to answering why this must be the case.

Here's a link to the relevant section of that wikipedia article: http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers.

 

[PAllen]

I disagree. The wiki article states the condition $5F_n^2 \pm 4$ must be a perfect square, but it doesn't do justice to answering why this must be the case.

Here's a link to the relevant section of that wikipedia article: http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers.

I agree it could say more.

 

[muzialis]

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?

 

[PAllen]

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 n²+/-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.

 

[D H]

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.

 

[muzialis]

Very usefuland interesting, many thanks to all.

 

[Borek]

Looks like something that can be proven by induction.

 

[D H]

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.

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 b_n is just the n^th 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
a_n = \begin{cases}<br /> 5F_n^2 + 4 &amp; \text{$n$ even} \\<br /> 5F_n^2 - 4 &amp; \text{$n$ odd}<br /> \end{cases}
In summary,
<br /> \phi^n = \frac {F_n\sqrt 5 + \sqrt{5F_n^2 \pm 4}} /2<br /> where +4 is used when n is even, -4 when n is odd.