设 $k$ 为大于 $1$ 的整数，数列 $\{a_n\}$ 定义如下：$a_{0}=0, a_{1}=1, a_{n+1}=k a_{n}+a_{n-1}, n=1,2, \cdots$．求所有满足如下条件的 $k$：存在非负整数 $l、m(l\ne m)$，及正整数 $p、q$，使得 $a_{l}+k a_{p}=a_{m}+ka_q$．
【难度】
【出处】
2010年中国西部数学奥林匹克试题
【标注】
【答案】
略
【解析】
结论是 $k= 2$．
当 $k=2$ 时，$a_{0}=0, a_{1}=1, a_{2}=2$，则由 $a_{0}+2 a_{2}=a_{2}+2 a_{1}=4$ 知：取 $l=0, m=2, p=2, q=1$ 即可．
对 $k\geqslant 3$，由递推式知：$\{a_n\}$ 为严格递增的整数数列且 $k|a_{n+1}-a_{n-1}$，即 $a_{2 n} \equiv a_{0}=0(\bmod k), a_{2 n+1} \equiv a_{1}=1(\bmod k)(n=0,1, \dots)$．①
若存在 $l, m \in \mathbf{N}, p, q \in \mathbf{N}^{*}, l \neq m$，满足 $a_{l}+k a_{p}=a_{m}+ka_q$，不妨设 $l<m$，分以下情况讨论：
（1）$p<l<m$．此时，$a_{l}+k a_{p} \leqslant a_{l}+k a_{l-1}<k a_{l}+a_{l-1}=a_{l+1} \leqslant a_{m}<a_{m}+k a_{q}$，矛盾!
（2）$l = p < m$．此时，若 $l=p=m-1$，则 $a_{m}+k a_{q}=a_{l}+ka_p=(k+1)a_{m-1}$，两边 $\bmod k$，得：$a_{m} \equiv a_{m-1}(\bmod k)$，由 ① 知，这是不可能的．
若 $l= P<m-1$，则 $a_{l}+k a_{p}<a_{m-2}+k a_{m-1}=a_{m}<a_{m}+k a_{q}$，矛盾!
（3）$l<p<m$．此时，注意到 $q\in N^{\ast}$，因而 $a_q > 0$，$a_{l}+k a_{p} \leqslant k a_{p}+a_{p-1}=a_{p+1} \leqslant a_{m}<a_{m}+k a_{q}$，矛盾!
（4）$l<m\leqslant p$．此时，$a_{p}>\dfrac{a_{l}+k a_{p}-a_{m}}{k}=a_{q}$．
由 $k a_{q}+a_{m}=k a_{p}+a_{l} \geqslant k a_{p}$ ②
知 $a_{q} \geqslant a_{p}-\dfrac{a_{m}}{k} \geqslant a_{p}-\dfrac{a_{p}}{k}=\dfrac{k-1}{k} a_{p}$ ③
注意到 $a_{p} \geqslant k a_{p-1}$ ④
所以 $a_{p}>a_{q} \geqslant \dfrac{k-1}{k} a_{p} \geqslant(k-1) a_{p-1} \geqslant a_{p-1}$ ⑤
由 ⑤ 知：$a_q = a_{p-1}$，所以 ②、③、④ 的等号都必须成立．由 ③ 知：$m= p$；由 ④ 知：$p = 2$，所以 $a_q=a_{p-1}=a_1=1$；由 ② 知：$l= 0$．
因此，由 $a_{l}+k a_{p}=a_{m}+k a_{q}$ 得：$k^{2}=k+k$，即 $k= 2$，矛盾！
所以，$k\geqslant 3$ 不满足题设，故 $k$ 只能取 $2$．
当 $k=2$ 时，$a_{0}=0, a_{1}=1, a_{2}=2$，则由 $a_{0}+2 a_{2}=a_{2}+2 a_{1}=4$ 知：取 $l=0, m=2, p=2, q=1$ 即可．
对 $k\geqslant 3$，由递推式知：$\{a_n\}$ 为严格递增的整数数列且 $k|a_{n+1}-a_{n-1}$，即 $a_{2 n} \equiv a_{0}=0(\bmod k), a_{2 n+1} \equiv a_{1}=1(\bmod k)(n=0,1, \dots)$．①
若存在 $l, m \in \mathbf{N}, p, q \in \mathbf{N}^{*}, l \neq m$，满足 $a_{l}+k a_{p}=a_{m}+ka_q$，不妨设 $l<m$，分以下情况讨论：
（1）$p<l<m$．此时，$a_{l}+k a_{p} \leqslant a_{l}+k a_{l-1}<k a_{l}+a_{l-1}=a_{l+1} \leqslant a_{m}<a_{m}+k a_{q}$，矛盾!
（2）$l = p < m$．此时，若 $l=p=m-1$，则 $a_{m}+k a_{q}=a_{l}+ka_p=(k+1)a_{m-1}$，两边 $\bmod k$，得：$a_{m} \equiv a_{m-1}(\bmod k)$，由 ① 知，这是不可能的．
若 $l= P<m-1$，则 $a_{l}+k a_{p}<a_{m-2}+k a_{m-1}=a_{m}<a_{m}+k a_{q}$，矛盾!
（3）$l<p<m$．此时，注意到 $q\in N^{\ast}$，因而 $a_q > 0$，$a_{l}+k a_{p} \leqslant k a_{p}+a_{p-1}=a_{p+1} \leqslant a_{m}<a_{m}+k a_{q}$，矛盾!
（4）$l<m\leqslant p$．此时，$a_{p}>\dfrac{a_{l}+k a_{p}-a_{m}}{k}=a_{q}$．
由 $k a_{q}+a_{m}=k a_{p}+a_{l} \geqslant k a_{p}$ ②
知 $a_{q} \geqslant a_{p}-\dfrac{a_{m}}{k} \geqslant a_{p}-\dfrac{a_{p}}{k}=\dfrac{k-1}{k} a_{p}$ ③
注意到 $a_{p} \geqslant k a_{p-1}$ ④
所以 $a_{p}>a_{q} \geqslant \dfrac{k-1}{k} a_{p} \geqslant(k-1) a_{p-1} \geqslant a_{p-1}$ ⑤
由 ⑤ 知：$a_q = a_{p-1}$，所以 ②、③、④ 的等号都必须成立．由 ③ 知：$m= p$；由 ④ 知：$p = 2$，所以 $a_q=a_{p-1}=a_1=1$；由 ② 知：$l= 0$．
因此，由 $a_{l}+k a_{p}=a_{m}+k a_{q}$ 得：$k^{2}=k+k$，即 $k= 2$，矛盾！
所以，$k\geqslant 3$ 不满足题设，故 $k$ 只能取 $2$．
答案
解析
备注
