Prove that Binet's formula gives an integer, using the binomial theorem I am given $$
F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}
$$
where, $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$.
The textbook states that it's equal to the $n$-th Fibonacci number $F_n$.
it is stated that since the Fibonacci numbers are integers, the number in $$
F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}
$$
is an integer as well. can you guys clarify this please?

How do I go on proving that the number
  $$F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$
   is an integer using Newton's Binomial Theorem? 

 A: How do I go on proving that the number in is an interger using Newton's Binomial Theorem?
$$\newcommand{\b}[1]{\left(#1\right)}
\newcommand{\d}{{\rm d}}
\newcommand{\f}{\frac}
\newcommand{\s}{\sqrt}
\newcommand{\t}{\text}
\newcommand{\u}{\underbrace}\bf Answer$$
$$S=\f1{\s5}\b{\b{\f{1+\s5}2}^n-\b{\f{1-\s5}2}^n}=\f1{2^n\s5}\b{\sum_{k=0}^n\binom5k5^{k/2}-\sum_{k=0}^n(-1)^k\binom5k5^{k/2}
}=\f1{2^n\s5}\sum_{k=0}^n[1-(-1)^k]\binom5k5^{k/2}$$
For when k is even the terms cancel so we get only odd terms let wherin we let $k=2t-1;k\in\{1,3,5,..n\},t\in\{1,2,..(n+1)/2\}$
$$S=\f1{2^{n-1}\s5}\sum_{t=1}^{(n+1)/2}\binom5{2t-1}5^{t-1/2}=\f1{2^{n-1}}\sum_{t=1}^{(n+1)/2}\binom5{2t-1}5^{t-1}$$
Now it's not irrational anymore and you may use induction.
A: I think this question was asked before.
First, using induction prove,

$$\Large{\phi^n = F_{n-1} + F_n \phi} \; \; \& \; \; \Large{\psi^n = F_{n-1} + F_n \psi}$$

Where $\phi = \frac{1 + \sqrt{5}}{2}$, and $\psi = 1 - \phi$.
Therefore,

$$\Large{\phi^n - \psi^n = F_{n-1} + F_n \phi -  F_{n-1} - F_n \psi} \\ \Downarrow \\ \Large{\phi^n - \psi^n = F_ n ( \phi - \psi ) = F_n \sqrt{5}} \\ \Downarrow \\ \Large{\frac{1}{\sqrt{5}} ( \phi^n - \psi^n ) = F_n }$$

$F_n $ is integer, therefore $\frac{1}{\sqrt{5}} ( \phi^n - \psi^n ) \; $ is also integer.
