Prove that $z^n + 1/{z^n}$ is a rational number 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!
 A: Hint $\ $ Exploit innate symmetry. For $\rm\:y = z^{-1}\:$ we know $\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 summetric polynomials.
A: Here is an uglier solution:
$$z+\frac{1}{z}=3 \Rightarrow z^2-3z+1=0 \Rightarrow z=\frac{3\pm \sqrt{8}}{2}$$
Note that $\frac{3-\sqrt{8}}{2}=\frac{1}{\frac{3+\sqrt{8}}{2}}$, thus $\{ z, \frac{1}{z} \} = \{ \frac{3+ \sqrt{8}}{2}, \frac{3- \sqrt{8}}{2} \}$.
Then 
$$z^n+\frac{1}{z^n}=\left( \frac{3 + \sqrt{8}}{2} \right)^n + \left( \frac{3 - \sqrt{8}}{2} \right)^n= \frac{1}{2^n} \left(\left( 3 + \sqrt{8} \right)^n + \left( 3 - \sqrt{8} \right)^n \right)\\
 =\frac{1}{2^n} \left(\sum_{k=0}^n \binom{n}{k} 3^{n-k} \sqrt{8}^k+\binom{n}{k} 3^{n-k} (-1)^k\sqrt{8}^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} 8^k\right)\\
$$
