I have been attempting to solve the following problem and am not sure if I have solved it correctly and how to prove a certain case at the end,
Let x be a real number such that $t = x + x^{−1}$ is an integer greater
than 2. Prove that $t_n = x^n + x^{−n}$ is an integer for all positive
integers n. Determine the values of n for which t divides $t_{n}$.
For the first part I noted that $t_{n+1} = t*t_n-t_{n-1}$ which is very simple to prove just by multiplying the ts together. Then I proved that $t_{2}$ was an integer employing a similar method to the formula and argued that $t_{n}$ must then be an integer by induction.
For the second part of the question I first considered $x+x^{-1} \cong 0\mod( x+x^{-1})$ which then implies $x\cong-x^{-1}$. With this fact consider $x^n + x^{-n}$ where n is odd. I get $x^{2k+1} + x^{-(2k+1)}\cong x^{2k+1} + (x^{-1})^{2k+1}\cong x^{2k+1} – x^{2k+1} \cong 0 \mod (x+x^{-1})$.
My question is then how do I prove that n cannot be even for t to divide $t_n$ and also is it okay to use modular arithmetic for this question since x is not actually an integer.
For the first bit I was thinking I could maybe do something with infinite descent since $t_{n+2}\cong -t_n$ so if t divides $t_n$ then it must divide all $t_{n}$ with the same parity. So if t doesn't divide $t_{2}$ there is a contradiction I'm just not sure how to show this.
Best Answer
Recall the identity
$$a^{n+1} + b^{n+1} = (a+b)(a^n + b^n) - ab(a^{n-1} + b^{n-1}).$$ So letting $a = x$, $b = 1/x$, then $ab = 1$ and we obtain $$x^{n+1} + x^{-(n+1)} = (x + x^{-1})(x^n + x^{-n}) - (x^{n-1} + x^{-(n-1)}),$$ or $$t_{n+1} = t_1 t_n - t_{n-1},$$ where I have slightly modified your notation: $t = t_1 = x + x^{-1}$. So, if $t$ is an integer, then $t_2$ is also an integer since $t_2 = t_1 t_1 - t_0$ and $t_0 = 2$ for any nonzero $x$. The rest follows by induction on $n$.
As for divisibility, note that if $t_1$ is an integer greater than $2$, then $t_1$ cannot divide $t_0 = 2$. So $t_2 = t_1^2 - t_0$ is not divisible by $t_1$. But $t_3 = t_1 t_2 - t_1$ is divisible by $t_1$, and $t_4 = t_1 t_3 - t_2$ is not. By now we can see the pattern: $t_n$ is divisible by $t_1$ if and only if $n$ is odd. I leave the formal proof of this fact as an exercise for the reader.