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?

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.