# Proving that $\frac{\phi^{400}+1}{\phi^{200}}$ is an integer.

How do we prove that $\dfrac{\phi^{400}+1}{\phi^{200}}$ is an integer, where $\phi$ is the golden ratio?

This appeared in an answer to a question I asked previously, but I do not see how to prove this..

We can prove by induction that

if $x+\dfrac1x$ is an integer, $x^n+\dfrac1{x^n}$ will be an integer

as $$\left(x^n+\frac1{x^n}\right)\left(x+\frac1x\right)=x^{n+1}+\frac1{x^{n+1}}+x^{n-1}+\frac1{x^{n-1}}$$

$$\iff x^{n+1}+\frac1{x^{n+1}}=\left(x^n+\frac1{x^n}\right)\left(x+\frac1x\right)-\left(x^{n-1}+\frac1{x^{n-1}}\right)$$

The base cases being

$n=1\implies x^2+\dfrac1{x^2}=\left(x+\dfrac1x\right)^2-2$ and
$x^3+\dfrac1{x^3}=\left(x+\dfrac1x\right)^3-3\left(x+\dfrac1x\right)$

or $n=2\implies x^3+\dfrac1{x^3}=\left(x^2+\dfrac1{x^2}\right)\left(x+\dfrac1x\right)-\left(x^1+\dfrac1{x^1}\right)$

As Golden Ratio$(\phi)$ satisfies $x^2-x-1=0$

we have $x^2-1=x\implies x-\dfrac1x=1\implies x^2+\dfrac1{x^2}=\left(x-\dfrac1x\right)^2+2=1^2+2$

Here $n=100$

• This is very slick. – Travis Willse Sep 18 '14 at 13:21
• Brilliant thinking! – user1001001 Sep 18 '14 at 13:22
• You can siplify your base cases: $x^0+\frac1{x^0}$ and $x^1+\frac1{x^1}$. – Hagen von Eitzen Sep 18 '14 at 13:22
• @HagenvonEitzen, Yes, definitely. But, these are too basic algebraic formulae – lab bhattacharjee Sep 18 '14 at 13:26
• Thank you very much for your help. – Sebastiano Dec 23 '20 at 21:47

We have $\phi^2=\phi+1$. We can use this to iterate powers of $\phi$. We have $\phi^3=2\phi+1$, $\phi^4=3\phi+2$, etc. We can iterate this, and finally obtain $$\frac{\phi^{400}+1}{\phi^{200}}=627376215338105766356982006981782561278127.$$ This is a squarefree composite number.

• For those who care, $627376215338105766356982006981782561278127 = 47 \times 1601 \times 3041 \times 124001 \times 6996001 \times 3160438834174817356001.$ – L. F. Mar 4 '19 at 9:39
• For those who care a little more, \begin{align} 627376215338105766356982006981782561278127&= 672303300609376277987^2 \\ &+ 413979435616172894178^2 \\ &+ 46374759 982260836093^2 \\ &+ 43068501847023435675^2 \end{align} – Mr Pie Apr 16 '19 at 6:43

$$\color{blue}{(\phi^2+\phi^{-2})}\in \mathbb N,$$ $$(\phi^2+\phi^{-2})^2=\color{blue}{(\phi^4+\phi^{-4})}+2\in \mathbb N,$$ $$(\phi^2+\phi^{-2})^3=\color{blue}{(\phi^6+\phi^{-6})}+3(\phi^2+\phi^{-2})\in \mathbb N,$$ $$(\phi^2+\phi^{-2})^4=\color{blue}{(\phi^8+\phi^{-8})}+4(\phi^4+\phi^{-4})+6\in \mathbb N,$$ $$(\phi^2+\phi^{-2})^5=\color{blue}{(\phi^{10}+\phi^{-10})}+5(\phi^6+\phi^{-6})+10(\phi^2+\phi^{-2})\in \mathbb N,$$$$...$$ $$(\phi^2+\phi^{-2})^{100}=\color{blue}{(\phi^{200}+\phi^{-200})}+100(\phi^{196}+\phi^{-196})+4950(\phi^{192}+\phi^{-192})+...\in \mathbb N.$$

• This is essentially @lab bhattacharjee's argument. – Yves Daoust Sep 18 '14 at 14:44
• We have the numbers $2, 3, 4, 5,\ldots, 100$ appear here, and then we also have the numbers $6, 10,\ldots , 4950$ for which these appear to be the triangular numbers. Is the latter correct? Can it be proven? – Mr Pie Apr 16 '19 at 6:48
• @user477343: come on, this is Pascal's triangle. – Yves Daoust Apr 16 '19 at 6:53
• Ooooohhhhh --- wait. Thinks again. Aaaahhhh... $\tiny\text{I don't get it}$ (just kidding xD) – Mr Pie Apr 16 '19 at 7:10

In general if $x+\dfrac1x$ is an integer then for all $n$, $x^n+\dfrac{1}{x^n}$ is an integer.

Both, $x$ and $\dfrac 1x$ are roots of the same equation $X^2-aX+1=0$ where $a$ is an integer. It follows that any equation deduced from it is also an equation of both $x$ and $\dfrac 1x$. We have $$X^2=aX-1$$ $$X^3=aX^2-X=a(aX-1)-X=(a^2-1)X-a$$ $$X^4=(a^2-1)X^2-aX=(a^2-1)(aX-1)-aX=(a^3-2a)X-(a^2-1)$$ For $X^n$ one has by iteration$$X^n=f_n(a)X+g_n(a)$$ where $f_n(a)$ and $g_n(a)$ are integers.

Since also $$\left(\frac{1}{X}\right)^n=f_n(a)\left(\frac{1}{X}\right)+g_n(a)$$ we conclude that $$x^n+\frac{1}{x^n}=f_n(a)(x+\frac1x)+2g_n(a)=af_n(a)+2g_n(a)\in\mathbb Z$$ (Note that this mode allows us to calculate the integer values of $x^n+\dfrac{1}{x^n}$).

More generally, $\dfrac{\phi^{2n}+1}{\phi^{n}}$ is an integer for $n$ even.

Indeed, let $n=2m$ and $\alpha=\phi^2$. Then $$\dfrac{\phi^{2n}+1}{\phi^{n}} = \phi^{n}+\dfrac{1}{\phi^{n}} = \alpha^{m}+\dfrac{1}{\alpha^{m}} =: y_m$$ Since $\alpha$ and $\dfrac{1}{\alpha}$ are the roots of $x^2=3x-1$, we have $y_{k+2} = 3y_{k+1}-y_{k}$ for all $k \in \mathbb N$.

Since $y_0=2$ and $y_1=3$ are integers, so is $y_k$ for every $k \in \mathbb N$.

In fact, $y_k=L_{2k}$, the $2k$-th Lucas number.

Yet more generally, $\dfrac{\phi^{2n}+(-1)^n}{\phi^{n}}$ is an integer for all $n \in \mathbb N$. In fact, it is the $n$-th Lucas number.

Using the golden ratio $\phi=\frac{1+\sqrt{5}}{2}$ and silver ratio $\psi=\frac{1-\sqrt{5}}{2}$, we get: $$\dfrac{\phi^{400}+1}{\phi^{200}}=\phi^{200}+\frac{1}{\phi^{200}}=\phi^{200}+\psi^{200}.$$ The Fibonacci formula: \begin{align}F_n&=\frac{\phi^n-\psi^n}{\sqrt{5}} \Rightarrow \\ \phi^{100}-\psi^{100}&=\sqrt{5}\cdot F_{100} \Rightarrow \\ \phi^{200}+\psi^{200}&=5F_{100}^2+2.\end{align} Note: $F_{100}=354224848179261915075$.