# Prove that $x^n+x^{-n} \in \mathbf{N}$ if $x+\frac1x \in \mathbf{N}$

Assume that $x+\frac{1}{x} \in \mathbb{N}$. Prove by induction that $$x^2+\frac1{x^2}, x^3+\frac1{x^3}, \dots , x^n+\frac1{x^n}$$ is also a member of $\mathbb{N}$.

I have my base, it is indeed true for $n=1$..

I can assume it is true for $x^k+x^{-k}$ and then proove it is true for $x^{k+1}+x^{-(k+1)}$ but I'm stuck there.

• Your statement is a little incorrect. You have to assume it's true for $x^k + x^{-k}$ and prove it's true for $x^{k+1} + x^{-k-1}$ Nov 21, 2013 at 22:11
• If you're allowed to invoke strong induction (i.e., "the hypothesis holds for every $n$ from $1$ to $k$"), then you can simply consider $(x+x^{-1})^{k+1}$.
– Blue
Nov 21, 2013 at 22:21

$$(x^n+x^{-n})(x+x^{-1})=x^{n+1}+x^{-(n+1)}+x^{n-1}+x^{1-n}\in\mathbb N$$
Let $a_n = x^n + \frac{1}{x^n}$. Then $x^2 = a_1x - 1$ implies $a_{n+2} = a_1a_{n+1} -a_n$ for all $n$.
Since $a_0=2$ and $a_1 \in \mathbb Z$, we have $a_n \in \mathbb Z$ for all $n \in \mathbb N$ by induction.