Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

I would appreciate your help.

share|improve this question
2  
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."? –  sos440 Mar 14 '12 at 1:20
5  
Why the downvote? –  user17762 Mar 14 '12 at 1:21

2 Answers 2

up vote 3 down vote accepted

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})$$

Look up Lucas sequences to learn more about such quadratic number theory.

share|improve this answer

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$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.