China Western Mathematical Olympiad

The answer is $k=2$. If $k=2$, then $a_0=0$, $a_1=1$, $a_2=2$, so $a_0+2a_2=a_2+2a_1=4$. Hence, $(\ell ,m)=(0,2)$ and $(p,q)=(2,1)$.

For $k\ge 3$, it follows from the recurrent relation that the sequence $\{a_n\}$ is strictly increasing, and $k\mid a_{n+1}-a_{n-1}$ for all $n\ge 1$. In particular, for $n\ge 0$, we have $$a_{2n}\equiv a_0\equiv 0(\mathrm{mod}k),a_{2n+1}\equiv a_1\equiv 1(\mathrm{mod}k).(\ast )$$ Suppose there exist $\ell ,m\in \mathbb{N}$, and $p,q\in {\mathbb{Z}}_{+}$ such that $\ell \ne m$ and $a_{\ell }+k{a}_p=a_m+k{a}_q$. We may assume that $\ell <m$, and divide into the following cases.

a. $p<\ell <m$: Then $a_{\ell }+k{a}_p\le a_{\ell }+k{a}_{\ell -1}<k{a}_{\ell }+a_{\ell -1}=a_{\ell +1}\le a_m<a_m+k{a}_q$, which contradicts the original assumption.

b. $\ell =p<m$: If $\ell =p=m-1$, then we have $a_m+k{a}_q=a_{\ell }+k{a}_p=(k+1)a_{m-1}$, and modulo $k$ we have $a_m\equiv a_{m-1}(\mathrm{mod}k)$, which contradicts $(\ast )$. If $\ell =p<m-1$, then $a_{\ell }+k{a}_p<a_{m-2}+k{a}_{m-2}=a_m<a_m+k{a}_q$, which contradicts the original assumption.

c. $\ell <p<m$: In this case, from $q$ we have $a_q>0$, then $a_{\ell }+k{a}_p\le k{a}_p+a_{p-1}=a_{p+1}\le a_m<a_m+k{a}_q$, which contradicts the original assumption.

d. $\ell <m\le p$: Then $a_p>\frac{a_{\ell }+k{a}_p-a_m}{k}=a_q$. It follows from $$k{a}_q+a_m=k{a}_p+a_{\ell }\ge k{a}_p①$$ that $$a_q\ge a_p-\frac{a_m}{k}\ge a_p-\frac{a_p}{k}=\frac{k-1}{k}{a}_p.②$$ Note that $$a_p=k{a}_{p-1}+a_{p-2}\ge k{a}_{p-\ell },③$$ hence $$a_p>a_q\ge \frac{k-1}{k}{a}_p\ge (k-1)a_{p-1}\ge a_{p-1}.④$$ Then by increasing property of $\{a_n\}$ and ④, we have $a_q=a_{p-1}$, so inequalities ①–③ turn into equalities. It follows from ② that $m=p$, and from ③ that $p=2$. Hence, $a_q=a_{p-1}=a_1=1$. And it follows from ① that $\ell =0$. From $a_{\ell }+k{a}_p=a_m+k{a}_q$, we have $k^2=k+k=2k$, so $k=2$, which is impossible.

So $k=2$ is the only solution. □