11
$\begingroup$

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

$\endgroup$
25
$\begingroup$

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$

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

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.

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

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

$\endgroup$
  • $\begingroup$ This is essentially @lab bhattacharjee's argument. $\endgroup$ – Yves Daoust Sep 18 '14 at 14:44
  • $\begingroup$ 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? $\endgroup$ – Mr Pie Apr 16 '19 at 6:48
  • $\begingroup$ @user477343: come on, this is Pascal's triangle. $\endgroup$ – Yves Daoust Apr 16 '19 at 6:53
  • $\begingroup$ Ooooohhhhh --- wait. Thinks again. Aaaahhhh... $\tiny\text{I don't get it}$ (just kidding xD) $\endgroup$ – Mr Pie Apr 16 '19 at 7:10
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.