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

[CynicusRex]

Homework Statement

Algebra I.M. Gelfand, problem 134.
You know that x+1/x is an integer. Prove that xⁿ+1/xⁿ is an integer for any n = 1, 2, 3, etc.

Homework Equations

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.

The base case of n = 1 is true, and suppose it holds for all k < n in order to do the induction step. Then
$$(x^{n-1}+1/x^{n-1})(x+1/x)=x^n+1/x^{n-2}+x^{n-2}+1/x^n=(x^n+1/x^n)+(x^{n-2}+1/x^{n-2})$$
so
$$x^n+1/x^n=(x^{n-1}+1/x^{n-1})(x+1/x)-(x^{n-2}+1/x^{n-2})$$
which is an integer, so the result follows by induction.

I don't get this part: "suppose it holds for all k < n"
Isn't that what you are supposed to prove?

 

[Orodruin]

Homework Statement

Algebra I.M. Gelfand, problem 134.
You know that x+1/x is an integer. Prove that xⁿ+1/xⁿ is an integer for any n = 1, 2, 3, etc.

Homework Equations

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?

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

 

[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.

 

[CynicusRex]

(...)

(...)

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.

 

[PeroK]

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.

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$).

 

[Stephen Tashi]

If I understand correctly; first you show cases n = 1, 2, 3 results in an integer,

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.

 

[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$.