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

• CynicusRex
In summary: So, the induction actually works in the following way: We assume that x+1/x is an integer, which we have already proven. Next, we show that xn+1/xn is an integer for any n. This is done by induction on n.
CynicusRex
Gold Member

## Homework Statement

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.

## 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?

## Homework Statement

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.

## 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

CynicusRex
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 and Orodruin
Stephen Tashi said:
(...)
Orodruin said:
(...)

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:
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##).

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

CynicusRex
...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##.

CynicusRex

## 1. What is the definition of induction in mathematics?

Induction is a mathematical proof technique used to demonstrate that a statement or property holds for all natural numbers, or in some cases, for all integers. It involves proving a base case and then showing that if the statement holds for some number, it also holds for the next number.

## 2. How is induction used to prove that x+1/x is an integer?

First, we prove that the statement holds for the base case, which is when x=1. When x=1, x+1/x=1+1/1=2, which is an integer. Next, we assume that the statement holds for some integer k. This means that k+1/k is also an integer. Then, we must show that the statement holds for k+1, which is (k+1)+(1/(k+1))=((k+1)^2+1)/(k+1). Using algebraic manipulation, we can show that this is equal to k+2+1/(k+1), which is an integer. Therefore, the statement holds for k+1, and by the principle of mathematical induction, it holds for all integers.

## 3. What is the statement that needs to be proven in this induction?

The statement that needs to be proven in this induction is that x+1/x is an integer for all integers x.

## 4. How does the proof for x^n+1/x^n being an integer differ from the proof for x+1/x?

The proof for x^n+1/x^n being an integer follows a similar process to the proof for x+1/x, but it involves using the binomial theorem and induction on the exponent n. The base case is when n=1, which is the same as the base case for x+1/x. Then, the induction hypothesis is that the statement holds for some integer k, which means that k^n+1/k^n is also an integer. Using the binomial theorem, we can expand (k+1)^n+1/k+1)^n and show that it is equal to k^n+1+1/k^n+1, which is an integer. Therefore, the statement holds for k+1, and by the principle of mathematical induction, it holds for all integers n.

## 5. Can induction be used to prove statements for non-integer values?

No, induction can only be used to prove statements for natural numbers or integers. This is because the principle of mathematical induction relies on the fact that every natural number has a successor, and therefore, we can always move onto the next number in the induction step. For non-integer values, there may not be a clear way to define the "next" value, and thus, induction is not applicable.

Replies
10
Views
718
Replies
4
Views
328
Replies
5
Views
964
Replies
17
Views
911
Replies
13
Views
2K
Replies
2
Views
920
Replies
11
Views
537
Replies
6
Views
1K
Replies
1
Views
1K
Replies
11
Views
728