Prove $z^n + 1/{z^n}$ is rational if $z+1/z$ is rational

Question

Knowing that $z + \frac{1}{z} = 3$ ($z \in \mathbb{R}$), prove that $z^n + \frac{1}{z^n} \in \mathbb{Q}$ ($n \in \mathbb{N}$ and $n \geq 1$).

I've tried to find a general formula for $z^n + \frac{1}{z^n}$. $$\left(z + \frac{1}{z}\right)^n = \binom{n}{0}z^n + \binom{n}{1}z^{n-2} + ... + \binom{n}{n-1}z^{2-n} + \binom{n}{n}z^{-n}$$ $$\left(z + \frac{1}{z}\right)^n = \binom{n}{0}(z^n + z^{-n}) + \binom{n}{1}(z^{n-2} + z^{2-n}) + ...$$

However, this formula seems to be wrong and I currently have no idea how to correct it and what to do next.

Thank you in advance for your help!

Answer 1

Hint $ $ Exploit innate $\rm\color{#c00}{symmetry}$. For $\rm\:y = z^{-1}\:$ we've $\rm\:\color{#c00}{yz,\ y+z\in\Bbb Q}.\,$ Now use the recurrence

$$\rm\quad\ \: y^{n+1}+z^{n+1}\ =\ (\color{#c00}{y+z})\ (y^n+z^n) -\ \color{#c00}{yz}\: (y^{n-1}+z^{n-1})\quad for\ \ all\ \ \ n \ge 0\qquad\quad $$

to deduce by induction that $\rm\,y^n+z^n\in\Bbb Q\,$ for all $\rm\,n\ge 0$.

Remark $ $ Above is a special case of Newton's identities for expressing power sums in terms of elementary $\rm\color{#c00}{symmetric}$ polynomials.

Answer 2

Here is an uglier solution:

$$z+\frac{1}{z}=3 \Rightarrow z^2-3z+1=0 \Rightarrow z=\frac{3\pm \sqrt{5}}{2}$$

Note that $\frac{3-\sqrt{5}}{2}=\frac{1}{\frac{3+\sqrt{5}}{2}}$, thus $\{ z, \frac{1}{z} \} = \{ \frac{3+ \sqrt{5}}{2}, \frac{3- \sqrt{5}}{2} \}$.

Then $$z^n+\frac{1}{z^n}=\left( \frac{3 + \sqrt{5}}{2} \right)^n + \left( \frac{3 - \sqrt{5}}{2} \right)^n= \frac{1}{2^n} \left(\left( 3 + \sqrt{5} \right)^n + \left( 3 - \sqrt{5} \right)^n \right)\\ =\frac{1}{2^n} \left(\sum_{k=0}^n \binom{n}{k} 3^{n-k} \sqrt{5}^k+\binom{n}{k} 3^{n-k} (-1)^k\sqrt{5}^k\right)\\ $$

Now, just observe that when $k$ is odd, the term inside the sum is $0$. This shows that

$$z^n+\frac{1}{z^n}= \frac{1}{2^n} \left(\sum_{k=0}^{\frac{n}{2}} \binom{n}{2k} 2 \cdot 3^{n-2k} 5^k\right)\\ $$