Find all sequences $(a_n)_{n\geq 1}$ of positive integers such that for all integers $n\geq 3$ we have $$ \dfrac{1}{a_1 a_3} + \dfrac{1}{a_2a_4} + \cdots + \dfrac{1}{a_{n-2}a_n}= 1 - \dfrac{1}{a_1^2+a_2^2+\cdots +a_{n-1}^2}. $$
Problem
Source: Iran second round 2024 p2
Tags: algebra and number theory
18.04.2024 14:26
The sequence is fibonacci
18.04.2024 14:56
Of course by checking the small values one could guess that $a_n$ is the Fibonacci sequence and prove this by induction.
19.04.2024 14:39
By checking the condition for $n=3$ , we have $a_1(a_1^2+a_2^2-1) | a_1^2+a_2^2$ and $(a_1^2+a_2^2-1) | a_1^2+a_2^2$ which means $a_1=a_2=1$ so there is at most one sequence satisfying that condition.And by the identity $F_1^2+...+F_n^2=F_n F_{n+1}$ and induction , the fibonacci sequence works.
29.04.2024 22:21
The only such sequence is the Fibonacci sequence. If $n=3$ we get, $$\frac{1}{a_1a_3}=1-\frac{1}{a_1^2+a_2^2}\Rightarrow \frac{1}{a_1a_3}+\frac{1}{a_1^2+a_2^2}=1$$The rightmost fraction is at most $\frac{1}{2}$ and the leftmost fraction is either $1$ or at most $\frac{1}{2}$. The only possibility is that both fractions are equal to $\frac{1}{2}$ and we get $(a_1,a_2,a_3)=(1,1,2)$. This leads us to try to prove $a_n=F_n$ by induction. We will use the well known identity $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$ in our induction. (This can be readily verified by a simple induction argument). Now we have, $$\dfrac{1}{a_1 a_3} + \dfrac{1}{a_2a_4} + \cdots + \dfrac{1}{a_{n-1}a_{n+1}}= 1 - \dfrac{1}{a_1^2+a_2^2+\cdots +a_{n}^2}.$$$$1-\frac{1}{F_{n-1}F_n}+\frac{1}{F_{n-1}a_{n+1}}=1-\frac{1}{F_{n}F_{n+1}}\Rightarrow \frac{1}{F_{n-1}a_{n+1}}=\frac{1}{F_{n-1}F_{n}}-\frac{1}{F_{n}F_{n+1}}=\frac{1}{F_{n-1}F_{n+1}}\Rightarrow a_{n+1}=F_{n+1}$$The induction is finished and the result follows.
08.05.2024 09:41
See also here https://artofproblemsolving.com/community/c6h3311885p30588644[\url]
02.07.2024 00:11
Claim: $$a_{n+1} = a_n + a_{n-1}$$Proof by induction is as follows: **Lemma 1**: for all natural n we have $$a_{n+1} = \frac{(\sum_{i=1}^{n} a_i^2) (\sum_{i=1}^{n-1} a_i^2)}{a_n^2 a_{n-1}}$$Proof: according to the given formula we have: $$ \dfrac{1}{a_1 a_3} + \dfrac{1}{a_2a_4} + \cdots + \dfrac{1}{a_{n-2}a_n}= 1 - \dfrac{1}{a_1^2+a_2^2+\cdots +a_{n-1}^2}. $$for all n, so similarly we have: $$ \dfrac{1}{a_1 a_3} + \dfrac{1}{a_2a_4} + \cdots + \dfrac{1}{a_{n-2}a_n} + \dfrac{1}{a_{n-1}a_{n+1}}= 1 - \dfrac{1}{a_1^2+a_2^2+\cdots +a_{n-1}^2+a_{n}^2}. $$If we substract these two from eachother, we'll have: $$\frac{1}{a_{n-1}a_{n+1}} = \dfrac{1}{a_1^2+a_2^2+\cdots +a_{n-1}^2} - \dfrac{1}{a_1^2+a_2^2+\cdots +a_{n}^2} = \frac{a_n^2}{(\sum_{i=1}^{n} a_i^2) (\sum_{i=1}^{n-1} a_i^2)} $$. So for all natural n we have: $$ a_{n+1} = \frac{(\sum_{i=1}^{n} a_i^2) (\sum_{i=1}^{n-1} a_i^2)}{a_n^2 a_{n-1}} $$ **Lemma 2**: For the Fibonnaci sequence we have $$\sum_{i=1}^{m} f_i^2 = f_m f_{m+1}$$Proof: by induction. For base of induction we have: $$f_1^2 = 1 = 1 × 1 = f_1 f_2$$$$f_1^2 + f_2^2 = 1 + 1 = 2 = 1 × 2= f_2 f_3$$$$f_1^2 + f_2^2 + f_3^2 = 1+ 1 +4 = 6 = 2 . 3 = f_3 f_4 $$Assuming it's true for m, we prove the case for m+1 : $$\sum_{i=1}^{m+1} f_i^2 = \sum_{i=1}^{m} f_i^2 + f_{m+1}^2 = f_m f_{m+1} + f_{m+1}^2 = f_{m+1}(f_m + f_{m+1}) = f_{m+1} f_{m+2}$$. Now we shall prove our problem. Base of induction: For n = 3 we have: $$ \frac{1}{a_1 a_3} = 1 - \frac{1}{a_1^2 + a_2^2} $$. Take $$ a_1 a_3 = x , a_1^2 + a_2^2 = y $$so our equation becomes $$ \frac{1}{x} = 1 - \frac{1}{y} \to y + x = xy \to (x-1)(y-1) = 1$$and because x and y are natural, then x-1=y-1=1. If x-1 = -1 then x = 0, which means at least one member of the sequence is zero, which is against the given conditions. Similar reasoning for y-1 = -1. So now we have x = y = 2 which gives us $$a_1 = a_2 = 1, a_3 = 2$$where 1+1 =2. Assumption: for all $$i \leq n$$we have $$a_i = f_i$$where $$f_i$$is the Fibonacci sequence. Proof for case = n+1 : By lemma 1 we have: $$ a_{n+1} = \frac{(\sum_{i=1}^{n} a_i^2) (\sum_{i=1}^{n-1} a_i^2)}{a_n^2 a_{n-1}} $$. By lemma 2 we have: $$\sum_{i=1}^{m} a_i^2 = a_m a_{m+1}$$for all $$m \leq n-1$$, so we have $$\sum_{i=1}^{n-1} a_i^2 = a_n a_{n-1}$$. Combining this with previous statement from lemma 1 we have: $$a_{n+1} = \frac{(\sum_{i=1}^{n} a_i^2) (\sum_{i=1}^{n-1} a_i^2)}{a_n^2 a_{n-1}} = \frac{(a_n^2 + a_n a_{n-1}) (a_n a_{n-1})}{a_n^2 a_{n-1}} = a_n + a_{n-1} = f_n + f_{n-1} = f_{n+1} $$which proves our claim. Therefore the only possible solution is the Fibonacci sequence.