# Fraction proof

• September 13th 2012, 11:35 AM
DIOGYK
Fraction proof
Hello everyone, I need your help with two problems, I would make separate threads for them but both are pretty much the same thing. They are from Gelfand's Algebra book.

Problem 133: You know that $x+\frac{1}{x}=7$. Compute (a) $x^2+\frac{1}{x^2}$; (b) $x^3+\frac{1}{x^3}$.

I solved problem 133 with quadratic equation and got the numbers but, since in this book, I haven't learned how to use quadratic equation yet, I think that this has to be solved by other way, in a way which will also help me to prove the next problem.

Problem 134: You know that $x+\frac{1}{x}$ is an integer. Prove that $x^n+\frac{1}{x^n}$ is an integer for any $n=1,2,3,etc.$

• September 13th 2012, 11:53 AM
DeMath
Re: Fraction proof
Hints:

${\color{red}\boxed{{\color{black}(a+b)^2=a^2+2ab+b ^2}}}$

\begin{aligned}\left(x + \frac{1}{x}\right)^2&= {x^2} + 2 \cdot x \cdot \frac{1}{x} + \frac{1}{{{x^2}}} = {x^2} + 2 + \frac{1}{{{x^2}}} \\ 7^2& = x^2 + 2 + \frac{1}{x^2}~ \Leftrightarrow~ {x^2} + \frac{1}{{{x^2}}} = {7^2} - 2 = \ldots \end{aligned}

${\color{red}\boxed{{\color{black}(a+b)^3=a^3+3a^2b +3ab^2+b^3}}}$

\begin{aligned} {\left( {x + \frac{1}{x}} \right)^3} &= {x^3} + 3 \cdot {x^2} \cdot \frac{1}{x} + 3 \cdot x \cdot \frac{1}{{{x^2}}} + \frac{1}{{{x^3}}} = {x^3} + 3\left( {x + \frac{1}{x}} \right) + \frac{1}{{{x^3}}} \\ {7^3} &= {x^3} + 3 \cdot 7 + \frac{1}{x^3}~ \Leftrightarrow~ x^3 + \frac{1}{x^3} = 7^3 - 3 \cdot 7 = \ldots \end{aligned}
• September 13th 2012, 11:55 AM
Plato
Re: Fraction proof
Quote:

Originally Posted by DIOGYK
Hello everyone, I need your help with two problems, I would make separate threads for them but both are pretty much the same thing. They are from Gelfand's Algebra book.
Problem 133: You know that $x+\frac{1}{x}=7$. Compute (a) $x^2+\frac{1}{x^2}$; (b) $x^3+\frac{1}{x^3}$.
I solved problem 133 with quadratic equation and got the numbers but, since in this book, I haven't learned how to use quadratic equation yet, I think that this has to be solved by other way, in a way which will also help me to prove the next problem.
Problem 134: You know that $x+\frac{1}{x}$ is an integer. Prove that $x^n+\frac{1}{x^n}$ is an integer for any $n=1,2,3,etc.$

Given $x+\frac{1}{x}=7$. Square both sides

$x^2+2+\frac{1}{x^2}=49$ or $x^2+\frac{1}{x^2}=47.$
• September 13th 2012, 11:05 PM
DIOGYK
Re: Fraction proof
Thank you DeMath and Plato, that was so easy, I feel stupid, I thought about squaring both sides but don't know why I didn't do it. Anyway, thanks for help.

I'm trying to do the next problem, that I also listed above, without luck.. because I have no experience with proofs, and there's lot's of proofs to do in this book, some are easy some are little harder, now I perfectly understand how to solve this problem by computing in higher powers, thanks to you, I've done it when n=4,5,6; but listing all of this solutions won't prove that every answer will be an integer, so can you also help me to write a proof?
• September 14th 2012, 12:59 AM
emakarov
Re: Fraction proof
Quote:

Originally Posted by DIOGYK
Problem 134: You know that $x+\frac{1}{x}$ is an integer. Prove that $x^n+\frac{1}{x^n}$ is an integer for any $n=1,2,3,etc.$

This can be proved by strong induction on n. (Strong induction because the induction step for n + 1 uses hypotheses for n and n - 1, not just for n.)
• September 14th 2012, 03:25 AM
DIOGYK
Re: Fraction proof
Quote:

Originally Posted by emakarov
This can be proved by strong induction on n. (Strong induction because the induction step for n + 1 uses hypotheses for n and n - 1, not just for n.)

First time I heard "strong induction" haha. I just read about it on some blogs, so I hope this is how I should do it:
I will show that $x^n+\frac{1}{x^n}=a$ where $a \subset N$ and $n=1,2,3,4$. Than I will let $k \geq 4$, and test if $x^n+\frac{1}{x^n}=a$ where $a \subset N$ is true for $k+1$ right? I will try this now.
• September 14th 2012, 03:44 AM
emakarov
Re: Fraction proof
Quote:

Originally Posted by DIOGYK
I will show that $x^n+\frac{1}{x^n}=a$ where $a \subset N$ and $n=1,2,3,4$. Than I will let $k \geq 4$, and test if $x^n+\frac{1}{x^n}=a$ where $a \subset N$ is true for $k+1$ right? I will try this now.

First, $a\subset N$ should be replaced with $a\in\mathbb{N}$. There is no need to use $a$ at all; just write $x^n+\frac{1}{x^n}\in\mathbb{N}$. It is sufficient to do the base case for n = 1 and 2. Then you prove

$\forall n\ge 2.\,\left(\forall k\le n.\,x^k+\frac{1}{x^k}\in\mathbb{N}\right)\to x^{n+1}+\frac{1}{x^{n+1}}\in\mathbb{N}$.

I.e., you fix $n$ and assume that $x^k+\frac{1}{x^k}\in\mathbb{N}$ for all $k\le n$. From that assumption you deduce that $x^{n+1}+\frac{1}{x^{n+1}}\in\mathbb{N}$. As was said above, it is sufficient to assume the induction hypotheses not for all $k\le n$, but for k = n and k = n - 1. Note that since you checked the statement for n = 1 and 2 in the base case and the induction step proceeds for $n\ge 2$, we have $n - 1\geq 1$, so the statements for n - 1 and n were established either in the base case or during the previous iteration of the induction step.
• September 18th 2012, 05:52 PM
DIOGYK
Re: Fraction proof
Quote:

Originally Posted by emakarov
First, $a\subset N$ should be replaced with $a\in\mathbb{N}$. There is no need to use $a$ at all; just write $x^n+\frac{1}{x^n}\in\mathbb{N}$. It is sufficient to do the base case for n = 1 and 2. Then you prove

$\forall n\ge 2.\,\left(\forall k\le n.\,x^k+\frac{1}{x^k}\in\mathbb{N}\right)\to x^{n+1}+\frac{1}{x^{n+1}}\in\mathbb{N}$.

I.e., you fix $n$ and assume that $x^k+\frac{1}{x^k}\in\mathbb{N}$ for all $k\le n$. From that assumption you deduce that $x^{n+1}+\frac{1}{x^{n+1}}\in\mathbb{N}$. As was said above, it is sufficient to assume the induction hypotheses not for all $k\le n$, but for k = n and k = n - 1. Note that since you checked the statement for n = 1 and 2 in the base case and the induction step proceeds for $n\ge 2$, we have $n - 1\geq 1$, so the statements for n - 1 and n were established either in the base case or during the previous iteration of the induction step.

Thanks for your effort emakarov, But I don't understand it. After I do the base case for n = 1 and 2, n can be any number more than 2, for example 6, how can I assume that $x^k+\frac{1}{x^k}\in\mathbb{N}$ for k=n or k=n-1, in this example 6 and 5. I think I don't even know what I am asking, I'm confused and I don't understand, can make it more clear for me.
Thanks.
• September 18th 2012, 07:27 PM
johnsomeone
Re: Fraction proof
For problem 134:

Let $a_n = x^n + \frac{1}{x^n}$. We're given that $a_1 = x + \frac{1}{x} = 7$.

Prove that $a_n$ is an integer for all $n \ge 0$ (thus actually for all $n \in \mathbb{Z}$ given the particually pretty symmetry).

Observe that, for any integer $n$:

$7a_n = \left(x + \frac{1}{x}\right) \left(x^n + \frac{1}{x^n}\right) = \left(x^{n+1} + \frac{1}{x^{n+1}}\right) + \left(x^{n-1} + \frac{1}{x^{n-1}}\right)$

$= a_{n+1} + a_{n-1}$. Thus $7a_n = a_{n+1} + a_{n-1}$.

THEREFORE $a_{n+1} = 7a_n - a_{n-1} \ \forall n \in \mathbb{Z}$

Since $a_0, a_1$, and $a_2$ are all integers (using problem 133), it's a trivial induction to show that $a_n \in \mathbb{Z} \ \forall n \in \mathbb{N}$ (so actually for all integers n).

Note that finding this recursion first, along with the obvious $a_0 = 2$ and $a_1 = 7$, would've solved problem 133 quickly ( $a_2 = 47, a_3 = 7(47) - (7) = 322$).
• September 18th 2012, 07:53 PM
Prove It
Re: Fraction proof
Quote:

Originally Posted by DIOGYK
Thanks for your effort emakarov, But I don't understand it. After I do the base case for n = 1 and 2, n can be any number more than 2, for example 6, how can I assume that $x^k+\frac{1}{x^k}\in\mathbb{N}$ for k=n or k=n-1, in this example 6 and 5. I think I don't even know what I am asking, I'm confused and I don't understand, can make it more clear for me.
Thanks.

I don't think you understand how induction works.

Think of a line of dominoes, and how it would look if this line extended indefinitely. It should be obvious that any domino falling over will push the next one, which will push the next, which will push the next, and continue pushing the next domino indefinitely. But this will only happen if the first domino is pushed in the first place.

Mathematical induction works the same way. You need to show that the statement is true for some base case (this is the equivalent of pushing over the first domino) and you also need to show an inductive step, that if an arbitrary case is true, that the next case will be true as well (this is the equivalent of any domino pushing the next one over).

In your case, you have already been told that \displaystyle \begin{align*} x + \frac{1}{x} \end{align*} is an integer. Your base case would be to show that \displaystyle \begin{align*} x^2 + \frac{1}{x^2} \end{align*} is an integer.

\displaystyle \begin{align*} x + \frac{1}{x} &= a, a \in \mathbf{Z} \\ \left(x + \frac{1}{x} \right)^2 &= a^2 \\ x^2 + 2 + \frac{1}{x^2} &= a^2 \\ x^2 + \frac{1}{x^2} &= a^2 - 2 \end{align*}

which is another integer, so the base case is true.

Now for the inductive step, we need to assume that the statement is true for some arbitrary value of \displaystyle \begin{align*} n \end{align*}, say \displaystyle \begin{align*} k \end{align*}, and prove that IF this is true, then the next one, \displaystyle \begin{align*} k + 1 \end{align*} will also be true.

So we are assuming \displaystyle \begin{align*} x^k + \frac{1}{x^k} = b, b \in \mathbf{Z} \end{align*} and using this to show \displaystyle \begin{align*} x^{k + 1} + \frac{1}{x^{k + 1}} = c, c \in \mathbf{Z} \end{align*}.

Does that make more sense? See if you can go from here?
• September 18th 2012, 08:52 PM
DIOGYK
Re: Fraction proof
Quote:

Originally Posted by Prove It
I don't think you understand how induction works.

Think of a line of dominoes, and how it would look if this line extended indefinitely. It should be obvious that any domino falling over will push the next one, which will push the next, which will push the next, and continue pushing the next domino indefinitely. But this will only happen if the first domino is pushed in the first place.

Mathematical induction works the same way. You need to show that the statement is true for some base case (this is the equivalent of pushing over the first domino) and you also need to show an inductive step, that if an arbitrary case is true, that the next case will be true as well (this is the equivalent of any domino pushing the next one over).

In your case, you have already been told that \displaystyle \begin{align*} x + \frac{1}{x} \end{align*} is an integer. Your base case would be to show that \displaystyle \begin{align*} x^2 + \frac{1}{x^2} \end{align*} is an integer.

\displaystyle \begin{align*} x + \frac{1}{x} &= a, a \in \mathbf{Z} \\ \left(x + \frac{1}{x} \right)^2 &= a^2 \\ x^2 + 2 + \frac{1}{x^2} &= a^2 \\ x^2 + \frac{1}{x^2} &= a^2 - 2 \end{align*}

which is another integer, so the base case is true.

Now for the inductive step, we need to assume that the statement is true for some arbitrary value of \displaystyle \begin{align*} n \end{align*}, say \displaystyle \begin{align*} k \end{align*}, and prove that IF this is true, then the next one, \displaystyle \begin{align*} k + 1 \end{align*} will also be true.

So we are assuming \displaystyle \begin{align*} x^k + \frac{1}{x^k} = b, b \in \mathbf{Z} \end{align*} and using this to show \displaystyle \begin{align*} x^{k + 1} + \frac{1}{x^{k + 1}} = c, c \in \mathbf{Z} \end{align*}.

Does that make more sense? See if you can go from here?

Yes it makes lots of sense, thanks!

I did this:

Since $x+\frac{1}{x}=a, a\in\mathbb{Z}$, and $x^k+\frac{1}{x^k}=b, b\in\mathbb{Z}$, $ab=(x+\frac{1}{x})(x^k+\frac{1}{x^k})=(x^{k+1}+ \frac{1}{x^{k+1}})+(x^{k-1}+\frac{1}{x^{k-1}})$.
So since we assumed that $x^k+\frac{1}{x^k}=b, b\in\mathbb{Z}$, this also assumes that $x^{k-1}+\frac{1}{x^{k-1}}=d, d\in\mathbb{Z}$, right? if so..
Since $a\in\mathbb{Z}$ & $b\in\mathbb{Z}$, $ab\in\mathbb{Z}$, and we assumed that $d\in\mathbb{Z}$, so $x^{k+1}+ \frac{1}{x^{k+1}}=ab-(x^{k-1}+\frac{1}{x^{k-1}})=ab-d$, which means that $x^{k+1}+ \frac{1}{x^{k+1}}\in\mathbb{Z}$, which means that $x^n+\frac{1}{x^n}\in\mathbb{Z}$ right? Is this proof accurate, if so, Big thanks to you Prove It, johnsomeone and emakarov : )
• September 18th 2012, 09:06 PM
Prove It
Re: Fraction proof
Quote:

Originally Posted by DIOGYK
Yes it makes lots of sense, thanks!

I did this:

Since $x+\frac{1}{x}=a, a\in\mathbb{Z}$, and $x^k+\frac{1}{x^k}=b, b\in\mathbb{Z}$, $ab=(x+\frac{1}{x})(x^k+\frac{1}{x^k})=(x^{k+1}+ \frac{1}{x^{k+1}})+(x^{k-1}+\frac{1}{x^{k-1}})$.
So since we assumed that $x^k+\frac{1}{x^k}=b, b\in\mathbb{Z}$, this also assumes that $x^{k-1}+\frac{1}{x^{k-1}}=d, d\in\mathbb{Z}$, right? if so..
Since $a\in\mathbb{Z}$ & $b\in\mathbb{Z}$, $ab\in\mathbb{Z}$, and we assumed that $d\in\mathbb{Z}$, so $x^{k+1}+ \frac{1}{x^{k+1}}=ab-(x^{k-1}+\frac{1}{x^{k-1}})=ab-d$, which means that $x^{k+1}+ \frac{1}{x^{k+1}}\in\mathbb{Z}$, which means that $x^n+\frac{1}{x^n}\in\mathbb{Z}$ right? Is this proof accurate, if so, Big thanks to you Prove It, johnsomeone and emakarov : )

Yes this looks fine :)