Question:
Suppose $ \frac{1}{x^2}+x^2$ is an integer. Prove that $ \frac{1}{x^{2n}}+x^{2n}$ is an integer for all natural $n$.
Hint: Use Strong Induction
My attempt:
Base Case is trivial.
I.H: Assume the result is true for $n = 1,2, ...., k.$
Consider $n = k+1$.
$ \frac{1}{x^{2\left(k+1\right)}}+x^{2\left(k+1\right)}\ =\ \frac{1}{x^{\left(2k+2\right)}}+x^{2k+2}$.
I am not sure what to do from here and how to use the induction hypothesis.
Hint: Use binomial expansion for -$$\left(x^2+\frac{1}{x^2}\right)^{n}$$
Solution: Group first and last terms, second and second last terms ... as follows - $$\left(x^2+\frac{1}{x^2}\right)^{n}=\binom{n}{0}\left(x^{2n}+\frac{1}{x^{2n}}\right)+\binom{n}{1}\left(x^{2n-2}+\frac{1}{x^{2n-2}}\right)+\ldots$$ and since $\dfrac{1}{x^{2k}}+x^{2k} \in \mathbb Z$ is true $\forall ~ 1\le k \le n-1$, you'll get $$x^{2n}+\frac{1}{x^{2n}}=\left(x^2+\frac{1}{x^2}\right)^{n}-\left(\binom{n}{1}\left( x^{2n-2}+\frac{1}{x^{2n-2}}\right)+\ldots\right) \in \mathbb Z$$
Note that $$\left(x^{2k}+\frac{1}{x^{2k}}\right)\left(x^{2}+\frac{1}{x^{2}}\right)=\left(x^{2(k+1)}+\frac{1}{x^{2(k+1)}}\right)+\left(x^{2k-2}+\frac{1}{x^{2k-2}}\right),$$now you can use induction to prove it without any difficulty.
By strong induction, let all
$$y_n:=\frac1{x^{2n}}+x^{2n}$$ be integers.
Then
$$y_1y_n-y_{n-1}=\left(\frac1{x^2}+x^2\right)\left(\frac1{x^{2n}}+x^{2n}\right)-\left(\frac1{x^{2n-2}}+x^{2n-2}\right)=\frac1{x^{2n+2}}+x^{2n+2}=y_{n+1}$$ is an integer.
The base case is
$$y_0=1+1,y_1=\frac1{x^2}+x^2$$ are integers.
With $a_n:=\frac 1{x^{2n}}+x^{2n}$, note that $$ a_1^n=\sum_{k=0}^n{n\choose k}\frac1{x^{2k}}x^{2(n-k)}=\sum_{k=0}^{\lfloor n/2\rfloor }{n\choose k}a_{n-2k}$$ (with $a_0=1$ understood). This can be solved to express $a_n$ in terms of previous terms.
Observe that
$(\dfrac{1}{x^2} + x^2)(\dfrac{1}{x^{2k}} + x^{2k}) = \dfrac{1}{x^{2(k + 1)}} + x^{2(k - 1)} + \dfrac{1}{x^{2(k - 1)}} + x^{2(k + 1)}$ $= (\dfrac{1}{x^{2(k + 1)}} + x^{2(k + 1)}) + (x^{2(k - 1)} + \dfrac{1}{x^{2(k - 1)}}), \tag{1}$
whence
$\dfrac{1}{x^{2(k + 1)}} + x^{2(k + 1)} = (\dfrac{1}{x^2} + x^2)(\dfrac{1}{x^{2k}} + x^{2k}) - (x^{2(k - 1)} + \dfrac{1}{x^{2(k - 1)}}) \tag{2}$
is an integer if
$(\dfrac{1}{x^2} + x^2)(\dfrac{1}{x^{2k}} + x^{2k}) \tag{3}$
and
$(x^{2(k - 1)} + \dfrac{1}{x^{2(k - 1)}}) \tag{4}$
are integers.
From here, induction will take off and fly on its own.
Here's a proof of a different flavor (probably not much easier if we include the proof of Newton's Identities). I am adding this just because it might perhaps provide some insight on why the result is true.
Suppose $\frac{1}{x^2} + x^2 = n$ for some $n \in \mathbb{Z}$.
Then $x^2$ and $\frac{1}{x^2}$ are roots of the polynomial $y^2 - ny + 1$.
Denote the roots by $r_1, r_2$ for readability.
By Vieta's formulas, $r_1 + r_2 = n$ and $r_1 r_2 = 1$.
We have $\frac{1}{x^{2n}} + x^{2n} = r_1^n + r_2^n$ which can be expressed as an integer polynomial of the elementary symmetric polynomials $r_1 + r_2$ and $r_1r_2$ (by Newton's Identities), and hence must be an integer as well.
