We consider the real sequence $(x_n)$ defined by $x_0=0, x_1=1$ and $x_{n+2}=3x_{n+1}-2x_n$ for $n=0,1,...$ We define the sequence $(y_n)$ by $y_n=x_n^2+2^{n+2}$ for every non negative integer $n$. Prove that for every $n>0$, $y_n$ is the square of an odd integer
Problem
Source: PAMO 2017 Problem 1
Tags: algebra, PAMO
Salty_Titanium
05.07.2017 20:38
I think there's a mistake. By your relation we get $x_{n + 1} = x_{n}$
atmchallenge
05.07.2017 20:46
Lemma 1: $x_n = 2^n -1$.
Proof: By induction. We see $x_0 = 2^0 -1, x_1 = 2^1 -1$, and thus the base cases are proved. Now suppose it holds for $x_{n-2}, x_{n-1}$. Then $x_n = 3x_{n-1} - 2x_{n-2} = 3\cdot 2^{n-1} - 3 - 2 \cdot x^{n-2} +2 = 3\cdot 2^{n-1} - 2^{n-1} -1 = 2^n -1$, as claimed, so by induction the claim holds true.
Then, by Lemma 1, $y_n = 2^{2n} - 2^{n+1} +1 + 2^{n+2} = 2^{2n} + 2^{n+1} + 1 = \left ( 2^n + 1 \right )^2$, and since $2^n+1$ is odd for all $n>0$, we are done.
Arasbulutiynemli
17.02.2020 19:40
Characteristic equation x*x=3*x-2 x*x-3*x+2=0 (x-1)(x-2)=0 x-1=1 x2=2 xn=k*(n power of 1)+m*(n power of 2) x0=k+m=0 x-1=k+2*m=1 m=1 k=-1 xn=(n power of 2) -1 yn=(2*n power of 2)+(n+1 power of 2)+1 yn=((n power of 2 +1)+1) * ((n power of 2 +1)+1)
Rukevwe
08.05.2023 11:36
Characteristic equation $x^2 = 3x -2$ $(x-1)(x-2) = 0$ $x = 1, 2$ Thus, $x_n = A \cdot 1^n + B \cdot 2^n$ $n = 0$ gives $A+B = 0$ $n=1$ gives $A+2B = 1$ So $A = -1, B = 1$. Then, $x_n = (-1) \cdot 1^n + 1 \cdot 2^n = 2^n -1$. And thus, $y_n = (2^n -1)^2 + 2^{n+2} = 2^{2n} + 2^{n+1} + 1 = (2^n + 1)^2$ , which is the square of an odd integer.$\square$