Let $k$ be an integer and $k > 1$. Define a sequence $\{a_n\}$ as follows: $a_0 = 0$, $a_1 = 1$, and $a_{n+1} = ka_n + a_{n-1}$ for $n = 1,2,...$. Determine, with proof, all possible $k$ for which there exist non-negative integers $l,m (l \not= m)$ and positive integers $p,q$ such that $a_l + ka_p = a_m + ka_q$.
Problem
Source:
Tags: inequalities, algebra proposed, algebra
01.11.2010 18:16
Answer: $k=2$. Obviously $\{a_n\}$ is strictly increasing. The equation $a_l+ka_p=a_m+ka_q$ is equivalent to $a_l-a_m=k(a_q-a_p)$. WLOG assume that $l>m$, so $q>p$. Also note that $a_{n+1}-a_n=(k-1)a_n+a_{n-1}\ge a_n-a_{n-1}$, so the sequence $\{a_1-a_0,a_2-a_1,a_3-a_2,\ldots\}$ is increasing. There are three cases: (i) $q\ge l+1$ \[a_l\ge a_l-a_m=k(a_q-a_p)\ge k(a_q-a_{q-1})\ge k(a_{l+1}-a_l)\] \[(k+1)a_l\ge ka_{l+1}\] For $l=0$ the above inequality is obviously wrong, so $l\ge1$ and we get: \[(k+1)a_l\ge k^2a_l+ka_{l-1}>(k+1)a_l\] which is a contradiction. (ii) $q\le l-1$ \[a_l-a_m=k(a_q-a_p)<ka_q\le ka_{l-1}\] For $l=1$ then $m=0$ and the above inequality becomes $1<0$ which is wrong. Therefore $l>1$ and hence \[a_l-a_m<a_l-a_{l-2}\] \[a_m>a_{l-2}\] \[m>l-2\] Since $m<l$ then $m=l-1$. We get $a_l-a_{l-1}=k(a_q-a_p)$. But the sequence $\{a_n\}$ in modulo $k$ is $\{0,1,0,1,0,1,\ldots\}$, so $k\not|a_l-a_{l-1}$, which is a contradiction. (iii) $q=l$ \[a_l-a_m=ka_l-ka_p\] \[(k-1)a_l=ka_p-a_m\le ka_p\le ka_{l-1}\] For $l=1$ the above inequality is wrong, so $l>1$ and \[(k-1)a_l\le a_l-a_{l-2}\] \[(k-2)a_l\le-a_{l-2}\] LHS is nonnegative and RHS is nonpositive, so both must be zero, we get $k=2$. For $k=2$, we take $l=2,m=0,p=1,q=2$.
01.11.2010 20:03
If you're not Johan Gunardi, disregard this post. JOHAN!!! Yang udah liat jawabannya jangan ngepost!!! Kasih kesempatan ke yang lain dong! XP
02.11.2010 13:04
It's okay
07.11.2010 06:36
Just out of curiosity, Johan, did you and your team members get less marks than expected? More than half of my team, including me, lost 15 marks randomly and we still don't know from where.
07.11.2010 06:57
oneplusone wrote: Just out of curiosity, Johan, did you and your team members get less marks than expected? More than half of my team, including me, lost 15 marks randomly and we still don't know from where. At the reverse, one member of our team gets 15 12 marks more than we expect.
07.11.2010 13:19
oneplusone wrote: Just out of curiosity, Johan, did you and your team members get less marks than expected? More than half of my team, including me, lost 15 marks randomly and we still don't know from where. We did a kind of coordination with the jury to avoid misinterpretation, as our first language is not English nor Chinese. So we know our marks for each problem, which were more or less the same as we expected.