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. 

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