Results 1 to 2 of 2

Math Help - Induction

  1. #1
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641

    Induction

    Quote Originally Posted by girlmatrix
    Hi I find out this problem from this webpage and solved it can you check it please and if I am in the correct way?

    Thanks for your advice and correction!!


    The problem is :

    You probably know the Fibonacci sequence (1, 1 , 2, 3,5,8…) but there is a lesser-known sequence called (Pythagoras stairs) generated by a similar recursion formula.

    This is a sequence of pairs (Xn,Yn) usually arranged as follows:
    1 2
    2 3
    5 7
    12 17

    And so on……. It begins with (x1,y1)=(1,1) and the recursion formula is

    X{n+1} = X{n} + Y{n}
    Y{n+1} = X{n}+ X{n+1}

    Prove by induction that always

    Y^2 = 2 X^2 ± 1

    Pythagoras used this equation to generate rational approximations to (2)^1/2


    The solution:


    To computing Y/X or Y(n)/X(n) gives an approximation to sq. rt (2) ,starting with (1,1).
    Y/X = sq.rt(2)
    => Y = X*(2)^(1/2)
    => Y^2 = 2X^2
    => Y^2 + XY = 2X^2 + XY
    =>Y/X = (2X + Y)/(X + Y)
    Then it can be written as (see your formulae) :
    Y(n + 1)/X(n + 1) = (2X(n) + Y(n))/(X(n) + Y(n))
    As it is true for n=1,2,3,4 so,let it be true for n=k i.e let for
    Y(k) / X(k) = (2X(k-1) + Y(k-1))/(X(k-1) + Y(k-1)) the formula Y(k)^2 = 2 X(k)^2 ± 1
    So for n= k+1,
    Y(k + 1)/X(k + 1) = (2X(k) + Y(k))/(X(k) + Y(k))
    => Y(k + 1)^2 / X(k + 1)^2 = (4X(k)^2 ± 4X(k) + Y(k)^2) / (X(k)^2 ± 2X(k) + Y(k)^2)
    => Y(k + 1)^2 / X(k + 1)^2 = 1 + (3X(k)^2 ± 2X(k)) / (X(k)^2 ± 2X(k) + Y(k)^2)
    => Y(k + 1)^2 / X(k + 1)^2 = 1 + (3X(k)^2 ± 2X(k)) /(3X(k)^2 ± 2X(k) ± 1)
    => Y(k + 1)^2 / X(k + 1)^2 = 1 + 1 -+ 1/(3X(k)^2 ± 2X(k) ± 1)
    => Y(k + 1)^2 / X(k + 1)^2 = 2 -+ 1/(3X(k)^2 ± 2X(k) ± 1)
    => Y(k + 1)^2 = 2X(k + 1)^2 -+ X(k + 1)^2 / (X(k) + Y(k))^2
    => Y(k + 1)^2 = 2X(k + 1)^2 -+1
    So, it is true for all n in N.
    I don't really have the time to do this, so I will post it for other people in case they want to answer it. (This was a PM to me)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2008
    Posts
    2

    Induction

    I think it is not the right solution!!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum