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.