Answer to Question #260145 in Discrete Mathematics for Anonymous

Question

Let α, β be roots of the equation x^2− 3x − 1 = 0. For each nonnegative integer n,

let y_n = α^n + β^n

. Show that gcd(y_n, y_(n+1)) = 1 for each nonnegative integer n.

Answer 1

Let's consider the equation $x^2-3x-1=0.$ The discriminant equals to $D=9+4=13$. So the equation has irrational roots: $\alpha=\frac{3+√3}{2}, \beta=\frac{3-√3}{2}$ . From the Viet theorem $\alpha+\beta=3, \alpha\beta=-1.$ If $n=0$ we have $y_0=\alpha^0+\beta^0=2$ . If $n=1$ we have $y_1=\alpha+\beta=3.$ So $gcd(y_0;y_1)=gcd(2;3)=1.$ In case $n=2$ we have $y_2=(\alpha+\beta)^2-2\alpha\beta=9+2=11, gcd(y_1;y_2)=1$ Let's prove that $y_n$ is natural and $gcd(y_n, y_{n+1})=1$ with the help of the method of mathematical induction. The base of induction is true. Let the proposition is true for all $n=1,...,k\in N$ , and $y_1,y_k \in N. gcd(y_{n-1},y_n)=1.$ If $n=k+1$ we have $y_{n+1}=(\alpha+\beta)y_n+\alpha\beta y_{n-1}$ . Si we have $y_{n+1} \in N.$ And $gcd(y_k, y_{k+1})=gcd(y_k,y_{k-1})=1.$