# Induction: x+1/x is an int. Prove that x^n+1/x^n is an int..

Tags:
1. Jan 16, 2017

1. The problem statement, all variables and given/known data
Algebra I.M. Gelfand, problem 134.
You know that x+1/x is an integer. Prove that xn+1/xn is an integer for any n = 1, 2, 3, etc.

2. Relevant equations

3. The attempt at a solution
I don't fully understand how the induction below proves anything. (Source)
I did attempt the solution, yet kept trying because I ignored similar answers to the one below, thinking I didn't prove anything.
I don't get this part: "suppose it holds for all k < n"
Isn't that what you are supposed to prove?

2. Jan 16, 2017

### Orodruin

Staff Emeritus
This is a basic induction proof. Take the case n=2. You have shown it is true for the basic case so it is true for all k<2. It therefore holds for 2. Now take n=3, you have shown it for 1 and 2 and so for all k<3 so it holds for n=3. Now take n=4, etc etc

3. Jan 16, 2017

### Stephen Tashi

The topic of induction is traditionally subdivided into the topics of "weak induction" and "strong induction".

In weak induction, the induction step is "Assume it's true for n-1. Show it's true for n"

In strong induction, the induction step is "Assume it's true for k = 1,2,...,n-1. Show it's true for n.

Statistically speaking, most induction problems encountered in math books can be done by using weak induction. Your example is an interesting illustration where a technique "in between" weak induction and strong induction can be used. In order to show the right hand side of the last equation is an integer, we must have assumed that $x^k + 1/x^k$ is an integer for the three cases $k=1, n-2, n-1$. Those 3 cases let us show that each term on the right hand side is an integer. The assumption of strong induction that $x^k + 1/ x^k$ is an integer for k = 1,2,3,...,n-3,n-2,n-1 is overkill, but it's sufficient to include the three cases we need.

You can consider whether the principle of "weak induction" can be used to prove the principle of "strong induction". That may clarify the distinction between the two techniques and cause you to believe the principle of "strong induction" - at least in cases where the index set involved is the positive integers.

4. Jan 17, 2017

If I understand correctly; first you show cases n = 1, 2, 3 results in an integer, so you can find that the following formula works $$x^3+1/x^3=(x^{3-1}+1/x^{3-1})(x+1/x)-(x^{3-2}+1/x^{3-2})$$ $$x^n+1/x^n=(x^{n-1}+1/x^{n-1})(x+1/x)-(x^{n-2}+1/x^{n-2})$$
whereafter you can deduce it will always result in an integer? Because if it's true for n=3, it will be true for n=4 as the formula for the latter will contain $$(x^3+1/x^3),~(x^2+1/x^2) ~and~(x+1/x)$$ which you have already shown to be an integer. And you can keep doing this for any n because the formula will always contain terms where the exponents are n-1, n-2 and n=1, which have—again—already been proven to be integers.

Last edited: Jan 17, 2017
5. Jan 17, 2017

### PeroK

Yes, although this question also includes another twist which is worth pointing out. In this case, we are assuming that $x + 1/x$ is an integer. Usually with induction, we will have some formula that can be proved to be true for $n =1$. In this problem, the case $n = 1$ is something we are assuming to be true (for some $x$).

6. Jan 17, 2017

### Stephen Tashi

You can do the proof that way. The way the proof was done didn't involve the detailed steps of showing the result was true for k = 2, 3. It only asserted the result was true for k = 1 and then did the strong induction step of assuming it was true for k = 1,2,3,...n-1. The way that you interpret the proof is a way of explaining to yourself why strong induction works.

7. Jan 17, 2017

### Stephen Tashi

...and you are correct that the proof should have established the result for the cases k = 2, 3 before it did the strong induction step since that step assumes n-1 and n-2 are each $\ge 1$.