MathDB
L 8

Source:

May 25, 2007
inductionLinear Recurrences

Problem Statement

Let {xn}n0\{x_{n}\}_{n\ge0} and {yn}n0\{y_{n}\}_{n\ge0} be two sequences defined recursively as follows x0=1,  x1=4,  xn+2=3xn+1xn,x_{0}=1, \; x_{1}=4, \; x_{n+2}=3 x_{n+1}-x_{n}, y0=1,  y1=2,  yn+2=3yn+1yn.y_{0}=1, \; y_{1}=2, \; y_{n+2}=3 y_{n+1}-y_{n}. [*] Prove that xn25yn2+4=0{x_{n}}^{2}-5{y_{n}}^{2}+4=0 for all non-negative integers. [*] Suppose that aa, bb are two positive integers such that a25b2+4=0a^{2}-5b^{2}+4=0. Prove that there exists a non-negative integer kk such that a=xka=x_{k} and b=ykb=y_{k}.