I'm reading the book How to prove it. I'm not sure about the correctness of my proof to this exercise.
We have to prove $ \forall n \in N(n\geq 1 \to x^n+1/x^n \text{ is an integer}) $ . We proceed by strong induction. Let $ n \in N $ be arbitrary and suppose $ \forall k<n(k\geq 1 \to x^k+1/x^k \text{ is an integer}) $. Suppose $ n\geq 1 $. Then we have the following cases:
Case 1: $ n=1 $. We already now that $ x+1/x $ is an integer.
Case 2: $ n>1 $. If we let $ k=n-1<n $, then by inductive hypothesis $ x^{n-1}+1/x^{n-1} $ is an integer. It follows that $ (x+1/x)(x^{n-1}+1/x^{n-1}) $ is also an integer. Expanding the product we get $ (x^{n}+{{1}\over{x^{n}}})+(x^{n-2}+x^{2-n}) $. Therefore $ x^{n}+{{1}\over{x^{n}}} $ is an integer, as required.
How can i be sure that $ x^{n}+{{1}\over{x^{n}}} $ is indeed an integer and not a real number?
Best Answer
There is a hole in the inductive step as given in the question, because strong induction on a statement $P(n)$ with a base case $n=1$ only gives you $P(k)$ for $1 \leq k \leq n - 1$ during the inductive step. And if all you know in the inductive step is that $n > 1,$ you don't know that $n - 2 \geq 1,$ therefore you cannot assume $P(n - 2)$ during the inductive step.
As it turns out, $P(0)$ is true for other reasons: $x^0 + 1/x^0$ is an integer (why?), which covers $P(n-2)$ when $n = 2,$ and when $n > 2$ then $n-2 \geq 1$ and $P(n-2)$ is covered by the strong induction assumption. So if you're careful, you can still complete the inductive step, but it requires two cases: one case for $n=2$ and another case for $n > 2.$
But you don't need strong induction. It is sufficient to use ordinary induction to prove a stronger statement: given that $x + 1/x$ is an integer,
$$ \forall n \in \mathbb N. (n \geq 1 \implies (\text{$x^n+1/x^n$ is an integer}) \land (\text{$x^{n+1}+1/x^{n+1}$ is an integer}). $$
Notice how your inductive proof uses only the "last two values of $n$", that is, from $k = n-1$ you get that $x^{n-1}+1/x^{n-1}$ is an integer and from $k = n-2$ you get that $x^{n-2}+1/x^{n-2}$ is an integer. You don't need to refer to any other values of $k$.
The stronger statement gives you two consecutive integers $x^k + 1/x^k$ and $x^{k+1} + 1/x^{k+1}$ during the inductive step, even for simple (not strong) induction, which is what you need. It also means you don't need to cover any special cases during the inductive step. The trade-off is that you must prove that $x^2 + 1/x^2$ is an integer for the base case. But if you look at what happens in your proof in the case $n=2,$ this part of the base case is easily dealt with.