# If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$

I am trying to solve the following exercise. If $x+\frac{1}{x}$ is a natural number, then $x^{n}+\frac{1}{x^{n}}$ is a natural number for all $n\in \mathbb{N}.$

Here what I've done. If $x+\frac{1}{x}$ and $x^{n}+\frac{1}{x^{n}}$ are natural numbers, then $(x+\frac{1}{x})(x^{n}+\frac{1}{x^{n}})\in \mathbb{N}$. But $(x+\frac{1}{x})(x^{n}+\frac{1}{x^{n}})=x^{n+1}+\frac{1}{x^{n-1}}+x^{n-1}+\frac{1}{x^{n+1}}$ and I got that $x^{n+1}+\frac{1}{x^{n+1}}\in \mathbb{N}$. But there is a problem here: I am not supposed to use the second principle of mathematical induction.

My question is: How does one prove that by using the first principle of mathematical induction?

-
If we let $a_n = x^n + x^{-n}$, how about proving the proposition "If $a_{n-1}$ and $a_n$ are natural numbers, then $a_n$ and $a_{n+1}$ are also natural numbers."? – Sangchul Lee Mar 14 '12 at 1:20
Why the downvote? – user17762 Mar 14 '12 at 1:21

Hint $\$ Put $\rm\ y = \frac{1}x\$ in: $\rm\ x+y,\: xy\in \mathbb Z\ \Rightarrow\ x^n+y^n\in \mathbb Z\:$ by induction, since

$$\rm x^{n+1}+y^{n+1}\ =\ (x+y)\: (x^n+y^n) - xy\: (x^{n-1} + y^{n-1})$$

-

By expanding $\big(x+\frac{1}{x}\big)^n$ using the binomial theorem and collecting terms of the form one gets $x^{k}+\frac{1}{x^{k}}$, one gets a proof using strong induction, that is, supposing that $x^{k}+\frac{1}{x^{k}}$ is an integer for all $k<n$.

-
Dear @lhf: Didn't the OP say he cannot use strong induction (which he/she calls the second principle of mathematical induction)? If strong induction were allowed, then the OP's approach is simpler than having to use the binomial theorem right? Not that I find your approach more difficult than the Op's. – Rankeya Mar 14 '12 at 4:10
@Rankeya, you're right. – lhf Mar 14 '12 at 11:39