Let $ \left(x_{n}\right)$ be a real sequence satisfying $ x_{0}=0$, $ x_{2}=\sqrt[3]{2}x_{1}$, and $ x_{n+1}=\frac{1}{\sqrt[3]{4}}x_{n}+\sqrt[3]{4}x_{n-1}+\frac{1}{2}x_{n-2}$ for every integer $ n\geq 2$, and such that $ x_{3}$ is a positive integer. Find the minimal number of integers belonging to this sequence.
Problem
Source: China Team Selection Test 2003, Day 2, Problem 3
Tags: induction, modular arithmetic, algebra, binomial theorem, algebra unsolved
30.12.2005 04:37
First, let's simplify everything a little by writing $a = \sqrt[3]{2}$ so we keep in mind that $a^3 = 2$. $x_{n+1} = \frac{ ax_n + 2a^2 x_{n-1} + x_{n-2} }{2}$ So we can find that $x_3 = \frac{ a^2 x_1 + 2a^2 x_1 + 0}{2} = \frac{3a^2}{2} x_1$ $x_1 = \frac{2}{3a^2} x_3 = \frac{a}{3} x_3$ for our integer $x_3$. Write the sequence in terms of $x_3$. $x_0 = 0$ $x_1 = \frac{a}{3} x_3$ $x_2 = \frac{a^2}{3} x_3$ $x_3 = x_3$ At this point, let's rewrite the recursion to make calculation easier. $x_{n+1} = \frac{ 3ax_n + 6a^2 x_{n-1} + 3x_{n-2} }{6}$ It should be clear now that the exponent of $a$ in $x_n$ is $n \bmod 3$, which means for $3 | n$ we have a rational coefficient of $x_3$. Now, let's calculate a few more terms. $x_4 = \frac{3a + 2a^4 + a}{6} x_3 = \frac{4a}{3} x_3$ $x_5 = \frac{4a^2 + 6a^2 + a^2}{6} x_3 = \frac{11a^2}{6} x_3$ $x_6 = \frac{5.5a^3 + 8a^3 + 3}{6} x_3 = 5x_3$, an integer. $x_7 = \frac{15a + 11a^4 + 4a}{6} x_3 = \frac{41a}{6} x_3$ $x_8 = \frac{20.5a^2 + 30a^2 + 5.5a^2}{6} x_3 = \frac{56a^2}{6} x_3$ $x_9 = \frac{28a^3 + 41a^3 + 15}{6} = \frac{153}{6} x_3$, not an integer. Conjecture: All $x_{3k}$ are non-integer for $k \ge 3$. This would mean the only integers in the squence are $x_0, x_3, x_6$. However, I am unsure if I have made a calculation mistake, and even if I haven't I lack the brainpower to complete the proof
30.12.2005 05:09
The offical solution is very very long and I am crazy to see it.The answer is 5,and $x_0,x_3,x_6,x_{12},x_{24}$ must be integers. The problem is created by a university professor and he's famous to create such crazy problem for MO and luckily he has retired.
30.12.2005 05:18
Calculation up to $x_{24}$ would be very tedious, and proving non-integer for all $x_{3k}, k > 8$ more tedious still - why write a problem that does not have elegant solution?!
30.12.2005 06:27
Solution:Suppose $n\geq2$,so \begin{eqnarray*} x_{n+1}-\sqrt[3]{2}x_n-\frac{1}{\sqrt[3]{2}}x_{n-1}&=&\frac{1}{\sqrt[3]{4}}x_n-\sqrt[3]{2}x_n+\sqrt[3]{4}x_{n-1}-\frac{1}{\sqrt[3]{2}}x_{n-1}+\frac{1}{2}x_{n-2}\\ &=&-\frac{\sqrt[3]{2}}{2}x_n+\frac{\sqrt[3]{4}}{2}x_{n-1}+\frac{1}{2}x_{n-2}\\ &=&-\frac{\sqrt[3]{2}}{2}(x_n-\sqrt[3]{2}x_{n-1}-\frac{1}{\sqrt[3]{2}}x_{n-2}) \end{eqnarray*} Since $x_2-\sqrt[3]{2}x_1-\frac{1}{\sqrt[3]{2}}x_0=0$, \[ x_{n+1}=\sqrt[3]{2}x_n+\frac{1}{\sqrt[3]{2}}x_{n-1}(n\geq1)\eqno (1) \] The character equation of (1) is $x^2=\sqrt[3]{2}x+\frac{1}{\sqrt[3]{2}}$ and the root is $x=\frac{\sqrt[3]{2}}{2}\pm\sqrt{\frac{\sqrt[3]{4}}{4}+\frac{1}{\sqrt[3]{2}}}=\frac{\sqrt[3]{2}}{2}(1\pm\sqrt{3})$ So by $x_0=0$,$x_n=A(\frac{\sqrt[3]{2}}{2})^n[(1+\sqrt{3})^n-(1-\sqrt{3})^n]$. $x_3=\frac{A}{4}[(1+\sqrt{3})^3-(1-\sqrt{3})^3]=3\sqrt{3}A$, So $A=\frac{x_3}{3\sqrt{3}}$. $x_n=\frac{x_3}{3\sqrt{3}}(\frac{\sqrt[3]{2}}{2})^n[(1+\sqrt{3})^n-(1-\sqrt{3})^n]$. Let $a_n=\frac{1}{\sqrt{3}}[(1+\sqrt{3})^n-(1-\sqrt{3})^n]$, $b_n=(1+\sqrt{3})^n+(1-\sqrt{3})^n$ It's east to show that $a_n$ is even and $b_n$ is also even. By $x_3$ is a positive integer,so the necessary condition of that $x_n$ is integer is $3|n$. And we also have for any nonnegative integer $m,n$ $a_{n+m}=\frac{1}{2}(a_nb_m+a_mb_n)$ $b_{n+m}=\frac{1}{2}(b_nb_m+3a_na_m)$ Let $m=n$, $a_{2n}=a_nb_n$ $b_{2n}=\frac{1}{2}(b_n^2+3a_n^2)$ Assume $a_n=2^{k_n}p_n,b_n=2^{l_n}q_n$,where $n,k_n,l_n$ is positive integer and $p_n,q_n$ are odd. We can get $a_1=b_1=2$,that means $k_1=l_1=1$.Then we can get $k_2=2,l_2=3,k_4=5,l_4=3,k_8=8,l_8=5$ And by induction \[ k_{2^m}=\left\{\begin{array}{cc} 1,&m=0\\ 2,&m=1\\ 2^{m-1}+m+1,&m\geq2 \end{array}\right.\\ l_{2^m}=\left\{\begin{array}{cc} 1,&m=0\\ 2,&m=1\\ 2^{m-1}+1,&m\geq2 \end{array}\right. \] For any $m_1>m_2\geq2$, $a_{2^{m_1}+2^{m_2}}=\frac{1}{2}(a_{2^{m_1}}b_{2^{m_2}}+a_{2^{m_2}}b_{2^{m_1}})$ $b_{2^{m_1}+2^{m_2}}=\frac{1}{2}(b_{2^{m_1}}b_{2^{m_2}}+3a_{2^{m_1}}a_{2^{m_2}})$ $k_{2^{m_1}+2^{m_2}}=2^{m_1-1}+2^{m_2-1}+m_2+1$ $l_{2^{m_1}+2^{m_2}}=2^{m_1-1}+2^{m_2-1}+1$ By induction,for $m_1>m_2>\ldots>m_r\geq2$ $k_{2^{m_1}+2^{m_2}+\ldots+2^{m_r}}=2^{m_1-1}+2^{m_2-1}+\ldots+2^{m_r-1}+m_r+1$ $l_{2^{m_1}+2^{m_2}+\ldots+2^{m_r}}=2^{m_1-1}+2^{m_2-1}+\ldots+2^{m_r-1}+1$ So if $n=2^rp$,where positive integer $r\geq2$,$p$ is odd, $k_n=\frac{n}{2}+r+1$ $l_n=\frac{n}{2}+1$ If $n=4m+1$, $a_{4m+1}=\frac{1}{2}(a_{4m}b_1+a_1b_{4m})=a_{4m}+b_{4m}$ So $k_{4m+1}=2m+1$. Likewise,$k_{4m+2}=k_{4m+3}=2m+2$ So \[ k_n=\left\{\begin{array}{cc} \frac{n+1}{2},&n \,\,\mbox{is odd}\\ \frac{n}{2}+1,&n\equiv2\pmod{4}\\ \frac{n}{2}+r+1,&n=2^rp,r\geq2,p \,\,\mbox{is odd} \end{array}\right. \] When $3|n$,$x_n=\frac{x_3}{3}2^{-\frac{2}{3}n}a_n=\frac{x_3}{3}2^{k_n-\frac{2}{3}n}p_n$ Since $a_3=12$,so $3|a_3$ and $3|a_{3\times2^r}$ where $r$ is nonnegative integer. $k_3=2=\frac{2}{3}\cdot3$ $k_6=4=\frac{2}{3}\cdot6$ $k_{12}=9>\frac{2}{3}\cdot12$ $k_{24}=16=\frac{2}{3}\cdot24$ So $x_3,x_6,x_{12},x_{24}$ are all integers. Let $x_3=3$,$x_n=2^{k_n-\frac{2}{3}n}p_n$. If $n\not\equiv0\pmod{4}$,then $k_n\leq\frac{n}{2}+1$. So for any $n>6$,$k_n-\frac{2}{3}n\leq1-\frac{n}{6}<0$. If $4|n$,suppose that $n=2^r3^kq$,where $r\geq2,k\geq1$,$3|q,2|q$. So $k_n=2^{r-1}3^kq+r+1$ $k_n-\frac{2}{3}n=2^{r-1}3^kq+r+1-2^{r+1}3^{k-1}q=r+1-2^{r-1}3^{k-1}q\leq r+1-2^{r-1}$ The equation holds iff $k=q=1$, So if $r>3$,$2^{r-1}=(1+1)^{r-1}>r+1$ Therefore when $r>3$,or$2\leq r\leq3$ and either $k$ or $q$ is larger than 1,we have $k_n-\frac{2}{3}n<0$. So if $x_3=3$,there is only five integer $x_0,x_3,x_6,x_{12},x_{24}$ in $\{x_n\}$. So the answer is 5. Crazy,isn't it?
30.12.2005 06:30
I've a friend who took part in this contest and failed in this problem,so he can't take part in IMO.And he hated the problem very much.
19.12.2006 17:26
It is easy to show $x_{n}=\frac{2^{-2n/3}((1+\sqrt{3})^{n}-(1-\sqrt{3})^{n})a}{3\sqrt{3}}$ when $x_{3}=a$. Of course, if xn is integer, then 3|n, and when number of natural integer in this sequence is minimum, then a=1 Let $y_{n}=x_{3n}, a=1$. then $y_{n+2}=5y_{n+1}+\frac{1}{2}y_{n}$ binomial theorem and power of 2 will give you a answer. only $y_{0},y_{1},y_{2},y_{4},y_{8}$ are integer. Is it hard?