Page 1 of 3 123 LastLast
Results 1 to 15 of 33

Math Help - Continued Fraction Expansion Problems

  1. #1
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200

    Continued Fraction Expansion Problems

    Hello All, I have some questions regarding Continued Fraction Expansion.

    As an initial reference, these problems have come from my textbook in the "additional examples" area. My book doesn't really give the best explanation of those examples all the time, and as a result I have a few questions.

    Q1. The numbers a_k can be found for 113/50 by using a continued fraction algorithm. Note that 113/50 is rational, and as a result it will have to terminate. Can anyone help me find this a_k ?

    Q2. Given the following, one should be able to form a continued fraction expansion for  e .

    We initially write (x,y,z,....) for the continued fraction of x + (1/(y+(1/(z+(1/...))))). From here, the continued fraction expansion for 2.718281828459045 is (2,1,2,1,1,4,1,1,6,1,1,8,1,1) . Knowing this, how many terms are necessary in order to accurately get 4 decimal places (2.718) ?

    Q3. Assume that x=Sqrt[3]-1. It can be proven that x = 1/(1+(1/(2+x))). Can somebody prove this? After it has been proven, the proof can be used to find the continued fraction expansion for x (Can somebody show this?). Next, find the continued franction expansion for Sqrt[3]. Once completed, a good accuracy check is that the first 6 or 7 terms of the expansion should give a reasonable approximation for Sqrt[3]. (The underlined portions are the questions I am asking).

    Q4. What is the continued fraction expansion of Sqrt[5]? My book notes that it might be helpful if "you find the continued fraction explansion of x where 0<x<1 and x is related to Sqrt[5].

    Q5. What is the continued fraction expansion of Sqrt[7]? My book notes that part of the expansion is (2,1,1,1,4,1,1,1,...). Is the next entry in this expansion a 2 or a 4 ? Also, it mentions that you can find some number like what I had mentioned in Q4, and once we have our answer we should be able to show why it is correct.

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    first question I will show you how u can find the continued fraction for 133/50

    \frac{113}{50} = 2.26

    i=2

    2.26 - 2 = .26

    \frac{26}{100}

    \frac{100}{26} = 3+ \frac{22}{26}
    3 is a_1

    \frac{26}{22} = 1 + \frac{4}{22}
    1 is a_2

    \frac{22}{4} = 5 + \frac{2}{4}

    a_3 = 5

    \frac{4}{2} = 2

    a_4 = 2 so the continued fraction is

    [i ; a_1 , a_2 , a_3 , a_4 ]
    [2; 3 , 1 , 5 , 2 ]

    Q2
    I think the best way is to find the continued fraction for 2.718 = r

    i =2

    r- 2 =718/1000

    1000/718 = 1 + 282/718

    718/282 = 2 + 154/282

    282/154 = 1 + 128/154

    154 /128 = 1 + 26/128

    128/26 = 4 + 24/26

    26/24 = 1 + 2/24

    24/2 = 12 end

    [2 ; 1, 2, 1, 1, 4, 1, 12 ]

    for more information see this

    http://en.wikipedia.org/wiki/Continued_fraction
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Amer View Post
    first question I will show you how u can find the continued fraction for 133/50

    \frac{113}{50} = 2.26

    i=2

    2.26 - 2 = .26

    \frac{26}{100}

    \frac{100}{26} = 3+ \frac{22}{26}
    3 is a_1

    \frac{26}{22} = 1 + \frac{4}{22}
    1 is a_2

    \frac{22}{4} = 5 + \frac{2}{4}

    a_3 = 5

    \frac{4}{2} = 2

    a_4 = 2 so the continued fraction is

    [i ; a_1 , a_2 , a_3 , a_4 ]
    [2; 3 , 1 , 5 , 2 ]

    Q2
    I think the best way is to find the continued fraction for 2.718 = r

    i =2

    r- 2 =718/1000

    1000/718 = 1 + 282/718

    718/282 = 2 + 154/282

    282/154 = 1 + 128/154

    154 /128 = 1 + 26/128

    128/26 = 4 + 24/26

    26/24 = 1 + 2/24

    24/2 = 12 end

    [2 ; 1, 2, 1, 1, 4, 1, 12 ]

    for more information see this

    Continued fraction - Wikipedia, the free encyclopedia
    Okay, I'm trying to follow along your work here.

    What is i ?

    Also for Q1 I take it a_k that I was looking for is a_4 = 2 (which terminates the algorithm) ?

    For Q2, I take it there are 7 terms necessary in order to get 4 digits of accuracy because there are 7 items in this array [2 ; 1, 2, 1, 1, 4, 1, 12 ] ?

    ------ Also, anyone have any ideas on the other questions or is able to confirm his Q1 and Q2 responses?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by Samson View Post
    Okay, I'm trying to follow along your work here.

    What is i ?

    Also for Q1 I take it a_k that I was looking for is a_4 = 2 (which terminates the algorithm) ?

    For Q2, I take it there are 7 terms necessary in order to get 4 digits of accuracy because there are 7 items in this array [2 ; 1, 2, 1, 1, 4, 1, 12 ] ?

    ------ Also, anyone have any ideas on the other questions or is able to confirm his Q1 and Q2 responses?
    i the integer part for the number that we want to find the continued fraction for it
    yeah a_4 terminated the algorithms

    Q2 is true 7 terms

    Q3

    x = \sqrt{3} -1

    x = \frac{1}{1+\frac{1}{2+x}}

    take the second

    x = \frac{1}{1+\frac{1}{2+x}}

    x = \frac{1}{\frac{2+x+1}{2+x}}

    x = \frac{2+x}{x+3}

    x(x+3) = 2+x

    x^2 +3x = 2+x \Rightarrow x^2+2x-2=0

    find x,then we are done

    how to write x =\sqrt{3}-1 in continued fraction using x = \frac{1}{1+ \frac{1}{2+x}}

    \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d  frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr  ac{1}{2+..}}}}}}}}}}

    I just sub x value each time it will never end

    \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d  frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr  ac{1}{2+..}}}}}}}}}}

    so

    \sqrt{3} = 1 +\dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d  frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr  ac{1}{2+..}}}}}}}}}}

    the continued fraction of sqrt{3} [1,2,1,2,1,2,...]
    first 6 terms will be (1,2,1,2,1,2)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Also, note that, given some set of numbers a_0, a_1, a_2, \dots a_n, if the series u_{n + 1} = u_n^{-1} + a_n converges towards your value, then the continued fraction expansion of this value is [a_n, a_{n - 1}, a_{n - 2}, \dots, a_0]. The reciprocal is true as well.

    That might give you a clue ...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Amer View Post
    i the integer part for the number that we want to find the continued fraction for it
    yeah a_4 terminated the algorithms

    Q2 is true 7 terms

    Q3

    x = \sqrt{3} -1

    x = \frac{1}{1+\frac{1}{2+x}}

    take the second

    x = \frac{1}{1+\frac{1}{2+x}}

    x = \frac{1}{\frac{2+x+1}{2+x}}

    x = \frac{2+x}{x+3}

    x(x+3) = 2+x

    x^2 +3x = 2+x \Rightarrow x^2+2x-2=0

    find x,then we are done

    how to write x =\sqrt{3}-1 in continued fraction using x = \frac{1}{1+ \frac{1}{2+x}}

    \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d  frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr  ac{1}{2+..}}}}}}}}}}

    I just sub x value each time it will never end

    \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d  frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr  ac{1}{2+..}}}}}}}}}}

    so

    \sqrt{3} = 1 +\dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d  frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr  ac{1}{2+..}}}}}}}}}}

    the continued fraction of sqrt{3} [1,2,1,2,1,2,...]
    first 6 terms will be (1,2,1,2,1,2)
    Okay, I'm a little lost with what you did here:
    x = \frac{1}{1+\frac{1}{2+x}}

    take the second

    x = \frac{1}{1+\frac{1}{2+x}}
    It looks like you have the same thing before and afterwards (unless I"m totally blind).

    How did you convert x=Sqrt[3]-1 to x = 1/(1+(1/(2+x))) ? It looks like you just wrote th first one then the second one and only used the second one. How did you connect them? Lastly, the first six terms are (1,2,1,2,1,2) but how do we ensure that that gives us 6 digits of accurracy (1.732050) ?

    Also, anyone have any input on Q4 and Q5?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    a good accuracy check is that the first 6 or 7 terms of the expansion
    not 6 decimal places

    x = \frac{1}{1+\frac{1}{2+x}}

    I called this second one if we solved it for x, we will get
    x=\sqrt{3}-1 and another one see

    x = \frac{1}{1+ \frac{1}{2+x}}

    x = \frac{1}{\frac{2+x+1}{2+x}}

    x = \frac{2+x}{3+x}

    x^2 +3x = 2+x

    x^2 + 2x -2 =

    x = \frac{-2\mp \sqrt{2^2 -4(1)(-2)}}{2(1)}

    x = \frac{-2 \mp \sqrt{12}}{2}

    x = \frac{-2 \mp 2\sqrt{3}}{2} = -1 \mp \sqrt{3}

    so x has two values \sqrt{3} -1 and -1-\sqrt{3}
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Amer View Post
    not 6 decimal places

    x = \frac{1}{1+\frac{1}{2+x}}

    I called this second one if we solved it for x, we will get
    x=\sqrt{3}-1 and another one see

    x = \frac{1}{1+ \frac{1}{2+x}}
    What does this even mean? "Called this second one if we solved it for x" ? I don't see how you got from one line to the other...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    omg

    Assume that x=Sqrt[3]-1. It can be proven that x = 1/(1+(1/(2+x))). Can somebody prove this?
    if I show that x=\sqrt{3}-1 is a solution for x =\frac{1}{1+ \frac{1}{2+x}}

    I'm done, is it ok for now, if it is then

    I sub \sqrt{3}-1 instead of x and want to show that the left hand side equal to the right hand side

    want to show
    \frac{1}{1+ \frac{1}{2+\sqrt{3}-1}}\;\; equal to \;\; \sqrt{3}-1

    \frac{1}{1+ \frac{1}{2+\sqrt{3}-1}}= \frac{1}{1+ \frac{1}{1+\sqrt{3}}}

    \frac{1}{1+ \frac{1}{1+\sqrt{3}}}  = \frac{1}{\frac{1+ \sqrt{3}}{1+\sqrt{3}} + \frac{1}{1+\sqrt{3}}}

    \frac{1}{\frac{1+ \sqrt{3}}{1+\sqrt{3}} + \frac{1}{1+\sqrt{3}}} = \frac{1}{\frac{1+\sqrt{3}+1}{1+\sqrt{3}}}

    \frac{1}{\frac{1+\sqrt{3}+1}{1+\sqrt{3}}} = \frac{1+\sqrt{3}}{2+\sqrt{3}}

    multiply the denominator and nominator by the conjugate of the denominator

     \frac{1+\sqrt{3}}{2+\sqrt{3}} = \left(\frac{1+\sqrt{3}}{2+\sqrt{3}}\right)\left(\f  rac{2 - \sqrt{3}}{2 - \sqrt{3}}\right)

    \left(\frac{1+\sqrt{3}}{2+\sqrt{3}}\right)\left(\f  rac{2 - \sqrt{3}}{2 - \sqrt{3}}\right) = \frac{2+2\sqrt{3}-\sqrt{3}-3}{2^2 - (\sqrt{3})^2}

    \frac{2+2\sqrt{3}-\sqrt{3}-3}{2^2 - (\sqrt{3})^2} = \frac{\sqrt{3} -1}{4 - 3} = \sqrt{3}-1

    end
    if something is not clear point it
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Here is an algorithm for Q4 and Q5. (Wikipedia - Methods of computing square roots - subheading Continued fraction expansion)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Thank you amer, I understand that was tedious of you to do but I'm very appreciative. I followed your steps this time but I was lost originally.

    undefined, as far as Q4 and Q5 goes, that wikipedia article had my head spinning for that example (114)... I figured 5 and 7 would be much easier.

    Somebody should be able to translate this garble for me (as I believe it has the answer right into it) if we can apply it to the questions I had asked:
    Square root of 5 - Wikipedia, the free encyclopedia

    As far as 7 goes, the book gave us part of the expansion (2,1,1,1,4,1,1,1,...). We just need to find out if the next entry in this expansion is a 2 or a 4 and show how we got there essentially.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Amer's Avatar
    Joined
    May 2009
    From
    Jordan
    Posts
    1,093
    Quote Originally Posted by Samson View Post
    Thank you amer, I understand that was tedious of you to do but I'm very appreciative. I followed your steps this time but I was lost originally. .
    it is not tedious but it is better to determine exactly what you do not understand, and do something not just asking try to understand.and show us some work
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by Amer View Post
    it is not tedious but it is better to determine exactly what you do not understand, and do something not just asking try to understand.and show us some work
    Well for Sqrt[5], the Wiki article shows [2;4,4,4,4,4,...] and they have it shown visually at the top of the page. How did they reach this conclusion though? How did they set it up?

    Sqrt[7] i'm lost on as well.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    This page does not describe how the continued fraction expansion of \sqrt{5} was obtained. (Ah, I see your newest post mentions this.) Best rational approximation is a separate topic, interesting in its own right. The best rational approximation of an irrational number for some upper limit d of denominator will always be either a convergent or a semiconvergent of the continued fraction expansion; the choice between convergent and semiconvergent can be determined using the so-called half rule.

    Computing square root continued fractions can be tricky to grasp, but if you review the sources and play around with all the numbers you will eventually see how it works. Post any specific questions.

    The description of algorithm in the link I gave you is ideal for computer programmers since it clearly specifies all the variables and how they change from one iteration to the next. On the other hand, it is not immediately clear where the algorithm came from.

    You can look at the example worked out in the problem statement of this Project Euler problem (#64) and see if it's any easier to follow.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Jun 2010
    From
    United States
    Posts
    200
    Quote Originally Posted by undefined View Post
    This page does not describe how the continued fraction expansion of \sqrt{5} was obtained. (Ah, I see your newest post mentions this.) Best rational approximation is a separate topic, interesting in its own right. The best rational approximation of an irrational number for some upper limit d of denominator will always be either a convergent or a semiconvergent of the continued fraction expansion; the choice between convergent and semiconvergent can be determined using the so-called half rule.

    Computing square root continued fractions can be tricky to grasp, but if you review the sources and play around with all the numbers you will eventually see how it works. Post any specific questions.

    The description of algorithm in the link I gave you is ideal for computer programmers since it clearly specifies all the variables and how they change from one iteration to the next. On the other hand, it is not immediately clear where the algorithm came from.

    You can look at the example worked out in the problem statement of this Project Euler problem (#64) and see if it's any easier to follow.

    I was able to follow along but I don't see why they chose the number '4' to start the expansion off with. I don't know how it relates to Sqrt[23]. Can someone start me off with how they got Sqrt[5]'s expansion? They give the answer but I'd like to know how they got there.

    As far as Q5 goes, I need similar help because I don't know how to get to the point to where they left off in the book.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 3 123 LastLast

Similar Math Help Forum Discussions

  1. Continued fraction expansion
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 20th 2011, 12:25 AM
  2. Value of a continued fraction.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 11th 2009, 11:12 AM
  3. continued fraction help ?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 10th 2008, 09:10 AM
  4. The continued fraction expansion for e
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 17th 2006, 06:22 AM
  5. continued fraction
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: October 16th 2006, 10:11 PM

Search Tags


/mathhelpforum @mathhelpforum