If $n$ is a natural number then how to show that $\frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{\sqrt{5}*2^n} $is also a natural number? This question is from Introduction to Analysis volume 1 by R. Courant, chapter 1, section 1.5, 9th question.
I tried using binomial theorem, root $5$ get an odd power in the numerator and can be cancelled by root $5$ in denominator but I don't have any idea how to get rid of those $n$ choose $k$ terms. 
 A: Hint:  
Let $F_n=\dfrac{(1+\sqrt5)^n-(1-\sqrt5)^n}{\sqrt5\cdot2^n}$.
$F_0=0$; $F_1=1$.
Can you show that $F_n=F_{n-1}+F_{n-2}$?
It might help to note that $(1+\sqrt5)^2=2(3+\sqrt5)$.
A: We derive  the formal power series   $\sum_{n=0}^\infty  F_nz^n$ with 
\begin{align*}
F_n=\frac{1}{2^n\sqrt{5}}\left(\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right),\quad n\geq 0\tag{1}
\end{align*}
We do some  calculations with its coefficients  and conclude that $F_n$ is  a natural   number for each $n\geq 0$.

We obtain
\begin{align*}
\color{blue}{\sum_{n=0}^\infty  F_nz^n}
&=\frac{1}{\sqrt{5}}\sum_{n=0}^\infty\left(\frac{1+\sqrt{5}}{2}\right)^nz^n
-\frac{1}{\sqrt{5}}\sum_{n=0}^\infty\left(\frac{1-\sqrt{5}}{2}\right)^nz^n\\
&=\frac{1}{\sqrt{5}}\,\frac{1}{1-\frac{1+\sqrt{5}}{2}z}-\frac{1}{\sqrt{5}}\,\frac{1}{1-\frac{1-\sqrt{5}}{2}z}\tag{2}\\
&=\frac{1}{\sqrt{5}}\frac{\left(1-\frac{1-\sqrt{5}}{2}z\right)-\left(1-\frac{1+\sqrt{5}}{2}z\right)}
{\left(1-\frac{1-\sqrt{5}}{2}z\right)\left(1-\frac{1+\sqrt{5}}{2}z\right)}\tag{3}\\
&\,\,\color{blue}{=\frac{z}{1-z(1+z)}}\tag{4}\\
\end{align*}

Comment:


*

*In (2) we do a  geometric series expansion.

*In (3) we write the expression with common  denominator.

*In (4) we do some simplifications.
Next we expand (4) into a geometric series and derive another representation of the coefficients $F_n$. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series.

We obtain from (4) for $n\geq 0$:
\begin{align*}
\color{blue}{F_n}&=[z^n]\frac{z}{1-z(1+z)}\\
&=[z^n]z\sum_{k=0}^\infty z^k(1+z)^k\tag{5}\\
&=\sum_{k=0}^{n-1}[z^{n-1-k}](1+z)^k\tag{6}\\
&=\sum_{k=0}^{n-1}[z^k](1+z)^{n-1-k}\tag{7}\\
&\,\,\color{blue}{=\sum_{k=0}^{n-1}\binom{n-1-k}{k}}\tag{8}
\end{align*}
We have in (8) another (well known) representation of the Fibonacci numbers $F_n$. Since $\binom{n-1-k}{k}$ are non-negative integers we conclude $F_n$ are natural numbers.

Comment:


*

*In (5) we do a geometric series expansion.

*In (6) we apply the rule $[z^p]z^qA(z)=[z^{p-q}]A(z)$. We also set the upper index of the sum to $n-1$ since other terms do not contribute.

*In (7) we change the order of summation $k\to n-1-k$.

*In (8) we select the coefficient of $z^k$.
A: We have that $$(1+\sqrt 5)^n-(1-\sqrt 5)^n=\sum_{k=0}^{n}\binom{n}{k}(\sqrt 5)^k-\sum_{k=0}^{n}\binom{n}{k}(-1)^k(\sqrt 5)^k=\sum_{k=0}^{n}\binom{n}{k}(\sqrt 5)^k[1-(-1)^k]=2^{\text{positive integer}}\sum_{0\le k\le n,\,k\,\text{odd}}\binom{n}{k}(\sqrt 5)^k.$$ Thus we have that $$\frac{(1+\sqrt 5)^n-(1-\sqrt 5)^n}{2^n\sqrt 5}=(\sqrt 5)^{-1}2^n2^{\text{positive integer}}\sum_{0\le k\le n,\,k\, \text{odd}}\binom{n}{k}(\sqrt 5)^k=2^{\text{positive integer}}\sum_{0\le k\le n,\,k \,\text{odd}}\binom{n}{k}(\sqrt 5)^{k-1},$$ which is clearly seen to be an integer since $k-1$ is even.
