Positive integers $a_1, a_2, \dots, a_{2023}$ satisfy the following conditions. $a_1 = 5, a_2 = 25$ $a_{n + 2} = 7a_{n+1}-a_n-6$ for each $n = 1, 2, \dots, 2021$ Prove that there exist integers $x, y$ such that $a_{2023} = x^2 + y^2.$
Problem
Source: KJMO 2023 P3
Tags: number theory, Sequence
05.11.2023 21:03
Assume $a_n$ can be written as x^2 + y^2 (with x>y, x even and 5(y^2 + 4) = (x+y)^2), and $a_{n+1}$ can be written as (2y + x)^2 + (2y + x/2)^2, then $a_{n+2}$ can be written as (5y + x/2)^2 + (6y+2x)^2. So basically there is a recurrence relation that send (y, x) to (2y + x/2, 2y + x).
19.01.2024 14:42
Can you please explain it to me?........
24.03.2024 19:00
This is my solution Let’s consider the numerical sequence F(n) such that F(n+2)=F(n+1)+F(n) for positive integer n, F(1)=1, F(2)=1 which is actually the Fibonacci sequence (lemma)F(2n)^2-F(2n)F(2n-1)-F(2n-1)^2=-1 for all positive integers n Proof)Let’s prove this equation by n-induction when n=1 it can be easily shown when n=k Let’s assume that that equation is satisfied when n=k+1 Let F(2k)=p, F(2k-1)=q F(2k+2)^2-F(2k+2)F(2k+1)-F(2k+1)^2 =(2p+q)^-(2p+q)(p+q)-(p+q)^2 =p^2-pq-q^2 =-1 Therefore, by n-mathematical induction, the lemma is proven. (solution) Let’s show that a(n)=(2F(2n-1))^2+(F(2n))^2 by n-induction case 1) when n=1 a(1)=(2*1)^2+1^2=5 case 2) when n=k(positive integer bigger than 1) Let’s assume that a(n)=(2F(2n-1))^2+(F(2n))^2 for all positive integers i such that i is not less than 1 and not bigger than k when n=k+1 a(k+1)=7a(k)-a(k-1)-6 by simple calculation (let F(2k+1)=a, F(2k+2)=b) we can get a(k+1)=10a^2+6ab-5b^2-6 since by lemma b^2-ab-a^2=-1 a(k+1)=-6(b^2-ab-b^2+1)+(2a)^2+(b)^2 =(2a)^2+(b)^2 =(2F(2k+1))^2+(F(2k+2))^2 Therefore, by n-mathematical induction in case 1&2 a(2023)=(2F(4045))^2+(F(4046))^2 integers x=2F(4045), y=F(4046) satisfies the problem (Q.E.D)