Thread: Induction

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)

I think it is not the right solution!!!!