# Condition for a number to be a Fibonacci one

1. May 30, 2014

### 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

2. May 30, 2014

### Staff: Mentor

These are not conditions, these are expressions.

3. May 30, 2014

### 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

4. May 30, 2014

### HallsofIvy

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

5. May 30, 2014

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

6. May 30, 2014

### D H

Staff Emeritus
The Binet formula gives a closed form solution for finding the nth Fibonacci number:
$$F_n = \frac{\phi^n - (-1/\phi)^{-n}}{\sqrt 5}$$or
$$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}$$
Solving for $\phi^n$ yields
$$\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}$$
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.

7. May 30, 2014

### PAllen

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

8. May 30, 2014

### D H

Staff Emeritus
9. May 30, 2014

### PAllen

10. May 30, 2014

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

11. May 30, 2014

### PAllen

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: May 30, 2014
12. May 30, 2014

### D H

Staff Emeritus
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.

13. May 30, 2014

### muzialis

Very usefuland interesting, many thanks to all.

14. May 30, 2014

### Staff: Mentor

Looks like something that can be proven by induction.

15. May 30, 2014

### D H

Staff Emeritus
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.

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