Induction problem 4


Suppose that \(\displaystyle x + \frac{1}{x}\) is an integer. We'll prove the claim by induction on n.

Base: When \(n = 1\), \(\displaystyle x^n + \frac{1}{x^n} = \displaystyle x + \frac{1}{x}\), which we know to be an integer. So the claim is true for the base case.

When \(n = 2\), consider \((\displaystyle x + \frac{1}{x})^2\). This is an integer because it's the square of an integer. Multiplying it out, we get $$(\displaystyle x + \frac{1}{x})^2 = x^2 + 2 + \frac{1}{x^2} = 2 + (x^2 + \frac{1}{x^2} )$$

So \((x^2 + \frac{1}{x^2})\) must be an integer because it's the difference of two integers.

Inductive hypothesis: Suppose that \(\displaystyle x^n + \frac{1}{x^n}\) is an integer for \(n=1,2,\ldots,k\).

Rest of the inductive step: We were given that \(\displaystyle x + \frac{1}{x}\) is an integer. From the inductive hypothesis, we know that \(\displaystyle x^k + \frac{1}{x^k}\) and \(\displaystyle x^{k-1} + \frac{1}{x^{k-1}}\) are integers.

Now, consider \((\displaystyle x + \frac{1}{x}) (\displaystyle x^k + \frac{1}{x^k})\) This is an integer because it's the product of two integers. If we multiply out this product, we get $$ (\displaystyle x + \frac{1}{x}) (\displaystyle x^k + \frac{1}{x^k}) = \displaystyle x^{k+1} + \frac{1}{x^{k-1}} + x^{k-1} + \frac{1}{x^{k+1}} = (\displaystyle x^{k+1} + \frac{1}{x^{k+1}}) + (x^{k-1} + \frac{1}{x^{k-1}}) $$

Since the whole thing is an integer and we know that \((x^{k-1} + \frac{1}{x^{k-1}})\) is an integer, \((\displaystyle x^{k+1} + \frac{1}{x^{k+1}})\) must be an integer, because it's the difference of two integers. This is what we needed to show.


The proof is short but not easy to construct. It's one of those problems where you need to see the trick.

Notice that the inductive step uses the truth of the claim at two previous values of n. So it's critical that our inductive hypothesis was strong, i.e. assumed the claim was true for all smaller values of n.

The claim is also true at \(n=0\). The above proof starts at \(n=1\) because the problem asked us to prove the claim only for positive integers. But it's not wrong to upgrade the claim to include all natural numbers.

Did you have only a single base case? Because the inductive step reaches two integers back, it's important to have two base cases.