<s>[INST] 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!
 [/INST] 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)\\
$$
</s>