Results 1 to 12 of 12
Like Tree7Thanks
  • 1 Post By DeMath
  • 1 Post By Plato
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By johnsomeone
  • 1 Post By Prove It
  • 1 Post By Prove It

Math Help - Fraction proof

  1. #1
    Junior Member DIOGYK's Avatar
    Joined
    Aug 2012
    From
    Norway
    Posts
    39

    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.

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member DeMath's Avatar
    Joined
    Nov 2008
    From
    Moscow
    Posts
    473
    Thanks
    5

    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}
    Last edited by DeMath; September 13th 2012 at 11:56 AM.
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,798
    Thanks
    1690
    Awards
    1

    Re: Fraction proof

    Quote Originally Posted by DIOGYK View Post
    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.
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member DIOGYK's Avatar
    Joined
    Aug 2012
    From
    Norway
    Posts
    39

    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Fraction proof

    Quote Originally Posted by DIOGYK View Post
    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.)
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member DIOGYK's Avatar
    Joined
    Aug 2012
    From
    Norway
    Posts
    39

    Re: Fraction proof

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: Fraction proof

    Quote Originally Posted by DIOGYK View Post
    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.
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member DIOGYK's Avatar
    Joined
    Aug 2012
    From
    Norway
    Posts
    39

    Re: Fraction proof

    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    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).
    Last edited by johnsomeone; September 18th 2012 at 07:38 PM.
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,672
    Thanks
    1497

    Re: Fraction proof

    Quote Originally Posted by DIOGYK View Post
    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?
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member DIOGYK's Avatar
    Joined
    Aug 2012
    From
    Norway
    Posts
    39

    Re: Fraction proof

    Quote Originally Posted by Prove It View Post
    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 : )
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,672
    Thanks
    1497

    Re: Fraction proof

    Quote Originally Posted by DIOGYK View Post
    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
    Thanks from DIOGYK
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: June 4th 2012, 05:02 AM
  2. Replies: 2
    Last Post: September 28th 2009, 07:18 PM
  3. Fraction proof
    Posted in the Algebra Forum
    Replies: 6
    Last Post: September 27th 2009, 04:24 PM
  4. Fraction Chain Inequality Proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 24th 2008, 09:15 AM
  5. Replies: 4
    Last Post: August 31st 2007, 11:05 PM

Search Tags


/mathhelpforum @mathhelpforum