Hint to prove that $\phi^n + \phi'^n$ is an integer.

Question

I was solving some induction exercises but I found this that I could not solve.

Let $n \in \mathbb{N}$, prove that $\phi^n + \phi'^n$ is an integer where $\phi=\frac{1+\sqrt{5}}{2}$ and $\phi'=\frac{1-\sqrt{5}}{2}=-\frac{1}{\phi}$.

Any hint for the inductive step?

Answer 1

Hint The inductive step will make use of $\varphi^2=\varphi+1$.

Answer 2

$\phi$ and $\phi'$ are roots of $x^2-x-1$ which has integer coefficients and so all symmetric polynomial functions of $\phi$ and $\phi'$ are polynomials over $\mathbb Z$ in the coefficients of $x^2-x-1$ and so are integers. $\phi^n + \phi'^n$ is one such symmetric polynomial function.

If you don't want to use the fundamental theorem of symmetric polynomials, you can use Newton's identities, which are exactly what you need and much easier to prove.

This solution does not use induction but is much more interesting.

Answer 3

Consider $1 = (\varphi + \frac{-1}{\varphi})^n$, use binomial expansion, and use induction.

Answer 4

Calculate the first 5 or 6 values of $a_n=\phi^n + \phi'^n$. Can you predict $a_n$ for larger $n$ values without calculating higher and higher powers of $\phi$ and $\phi'$? Do you see a pattern to the numbers in the sequence $\{a_n\}$? Can you prove it's true for $\phi^n + \phi'^n$? Will a previously-offered hint help you do that?