The sequence $ (x_n)$ is defined by $ x_1=1,x_2=a$ and $ x_n=(2n+1)x_{n-1}-(n^2-1)x_{n-2}$ $ \forall n \geq 3$, where $ a \in N^*$.For which value of $ a$ does the sequence have the property that $ x_i|x_j$ whenever $ i<j$.
Problem
Source: Romania TST 1995
Tags: number theory proposed, number theory
18.09.2009 19:14
hello, i have found $ x_n=\frac{n!}{12}(20-6n+3na-4a-2n^2+n^2a)$. Sonnhard.
21.01.2021 18:51
I claim $a=2,4$ is the answer. Note that $x_3=7x_2-8$. Hence, for $x_i\mid x_j$ to hold for every $i<j$, one can immediately see that $a\mid 8$. Thus $a\in\{1,2,4,8\}$. Case 1: $a=1$. In this case we find $x_4=-24$, $x_5=-240$ and $x_6 =13x_5-35x_4$. Hence for $x_5\mid x_6$ to hold, it must also hold that $-240\mid 35\cdot 24$, which is not possible. Hence $a=1$ does not work. Case 2: $a=2$. In this case, we inspect first few terms, and observe that $x_n=n!$ for smaller values of $n$. We prove this by induction. If $x_{n-1}=(n-1)!$ and $x_{n-2}=(n-2)!$ then \[ x_n = (2n+1)(n-1)! - (n-1)(n+1)(n-2)! =n!, \]as claimed. In this case $x_i\mid x_j$ indeed hold for every $i<j$. Case 3: $a=4$. Again, we observe $x_n/x_{n-1} = (n+2)$, which leads to the conclusion that $x_n=(n+2)!/6$. This is also easily proven by induction, hence the condition holds. Case 4: $a=8$. In this case, $x_2=8$, $x_3=48$ and $x_4=9x_3-15x_2$. For $x_3\mid x_4$ to hold, it must hold that $x_3=48\mid 15x_2 = 120$, which clearly does not hold. Hence the answer is indeed $a=2,4$, as claimed.