Fibonacci General Formula - Is it obvious that the general term is an integer?

Question

Given the recurrence relation for the Fibonacci numbers, $F_{n+1}=F_{n}+F_{n-1}$ with $F_0=1$ and $F_1=1$ it's obvious that $F_n$ is a positive integer for all $n$. Suppose instead we were given $$F_n=\frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n$$ Without spotting that $F_{n+1}=F_{n}+F_{n-1}$, how might one show that $F_n$ is an integer for all $n$?

Answer 1

A few ideas.

1: It's natural to multiply the right-hand side by $1=(1+\sqrt5)/2+(1-\sqrt5)2$ and see what happens. In this case, it turns the expression for $F_n$ into the expression for $F_{n+1}-F_{n-1}$, which you might not like for these purposes - but it does allow one to show that $F_{n+1}$ is an integer, by induction.

2: As ploosu2 mentioned, expanding everything using the binomial theorem shows that $F_n$ is rational; moreover, the only prime that can divide its denominator is $2$. So a careful analysis of the powers of $2$ dividing everything might succeed.

3: The expression is invariant under changing $\sqrt5$ to $-\sqrt5$. So Galois theory tells us that it's rational at least. In fact, everything in sight is an algebraic integer except the $1/\sqrt5$; so at worst the denominator is $5$. A more careful analysis might find a way to get rid of that $5$.

Combine 2 and 3 if you want, for that matter....

Answer 2

Without spotting initially the recurrence formula but knowing the theory of recurrence relations:

Because has the form $A\alpha^n+B\beta^n$, is obviously solution of a recurrence equation with characteristic polynomial $(x-\alpha)(y-\beta)=x^2-x-1$ in this case. This gives the recurrence relation.