Hi,hxy09 Have you tried the method in http://www.mathlinks.ro/viewtopic.php?t=26797 ? Or http://www.mathlinks.ro/viewtopic.php?t=4556 ?

My idea was same to you,and I am familiar to these two links But I didn't solve it even I have worked on it for more than two and a half hours!!! Unfortunately,it was said that the solution was not "analysis" as the previous two links.

And then maybe you can check if my solution is right(or 1 point?).I am really confused about it. Sorry for not using Latex. Let c1>c2>c3, d1>d2>d3,and {c1,c2,c3}={a1,a2,a3},{d1,d2,d3}={b1,b2,b3} Let {f1(n),f2(n),f3(n)}={f4(n),f5(n),f6(n)}={n+1,n,n-1} And f1(n)c1^n+f2(n)c2^n+f3(n)c3^n=(n+1)a1^n+na2^n+(n-1)a3^n f4(n)d1^n+f5(n)d2^n+f6(n)d3^n=(n+1)b1^n+nb2^n+(n-1)b3^n Then do something as metioned above... We can assume that (f4(n)d1^n+f5(n)d2^n+f6(n)d3^n)/(f1(n)c1^n+f2(n)c2^n+f3(n)c3^n)=sum(Pi(n)/Qi(n)*ri^n) i=1,2,...,k where Pi(x),Qi(x) (i=1,2,...,k) are rational coefficient polynomial ,and Qi(x) (i=1,2,...,k) are monic. And r1>r2>...>rk>=1 ,which are rational. Then do something like Gauss's Lemma(here) We know Qi(x)=1 (i=1,2,...,k) Then f4(n)d1^n+f5(n)d2^n+f6(n)d3^n=(f1(n)c1^n+f2(n)c2^n+f3(n)c3^n)sum(Pi(n)*ri^n) i=1,2,...,k Then we know f1(x)=f4(x),f3(x)=f6(x),f2(x)=f5(x) We can get the result by simple calculation.

I will give you more details if you want. I just wonder if my solution is correct.

I was thinking about analysis all the time during the contest... Indeed,we can play the same trick as http://www.mathlinks.ro/viewtopic.php?p=466215#p466215 Not that difficult,right?

Attachments:

OK,I will show you the first step. $ \frac {f_4(n)d_1^{n} + f_5(n)d_2^{n} + f_6(n)d_3^{n}}{f_1(n)c_1^{n} + f_2(n)c_2^{n} + f_3(n)c_3^{n}}$ $ = \frac {\frac {f_4(n)}{f_1(n)}(\frac {d_1}{c_1})^{n} + \frac {f_5(n)}{f_1(n)}(\frac {d_2}{c_1})^{n} + \frac {f_6(n)}{f_1(n)}(\frac {d_3}{c_1})^{n}}{1 + \frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n}}$ when $ n$ is sufficiently large , $ \frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n} < 1$ $ \frac {\frac {f_4(n)}{f_1(n)}(\frac {d_1}{c_1})^{n} + \frac {f_5(n)}{f_1(n)}(\frac {d_2}{c_1})^{n} + \frac {f_6(n)}{f_1(n)}(\frac {d_3}{c_1})^{n}}{1 + \frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n}}$ $ = (\frac {f_4(n)}{f_1(n)}(\frac {d_1}{c_1})^{n} + \frac {f_5(n)}{f_1(n)}(\frac {d_2}{c_1})^{n} + \frac {f_6(n)}{f_1(n)}(\frac {d_3}{c_1})^{n})(1 - (\frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n}) + (\frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n})^{2} - ...... + (\frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n})^{2M} + O((\frac {f_2(n)}{f_1(n)}(\frac {c_2}{c_1})^{n} + \frac {f_3(n)}{f_1(n)}(\frac {c_3}{c_1})^{n})^{2M + 1}) )$ where $ M$ satisfied $ \frac {d_1c_2^{2M + 1}}{c_1^{2M + 2} } < 1$ Expand it. $ \frac {f_4(n)d_1^{n} + f_5(n)d_2^{n} + f_6(n)d_3^{n}}{f_1(n)c_1^{n} + f_2(n)c_2^{n} + f_3(n)c_3^{n}}$ can be written as $ \sum_{i = 1}^{k}\frac {P_i(n)}{Q_i(n)}r_i^{n} + O((1 - \epsilon_1)^n)$ where $ P_i(x)$,$ Q_i(x)$ ($ i = 1,2,...,k$) are rational coefficient polynomial ,and $ Q_i(x)$ ($ i = 1,2,...,k$) are monic(and $ Q_i(x) = f_1(x)^{t}$). [Once I made a small mistake here.I claimed that Pi(x) and Qi(x) have the form r(n+1)^a*n^b*(n-1)^c ,which is certainly wrong for Pi(x).] And $ r_1 > r_2 > ... > r_k\ge1$ ,which are rational. Now that $ \frac {f_4(n)d_1^{n} + f_5(n)d_2^{n} + f_6(n)d_3^{n}}{f_1(n)c_1^{n} + f_2(n)c_2^{n} + f_3(n)c_3^{n}} \in Z$ So $ \sum_{i = 1}^{k}\frac {P_i(n)}{Q_i(n)}r_i^{n} + O((1 - \epsilon_1)^n) \in Z$ Then $ \sum_{i = 1}^{k}P_i(n)\frac {[Q_1(n),Q_2(n),...,Q_k(n)]}{Q_i(n)}r_i^{n} + O((1 - \epsilon_2)^n) \in Z$ where $ 0 < \epsilon_2 < \epsilon_1$ Let $ F(n) = [Q_1(n),Q_2(n),...,Q_k(n)]\frac {f_4(n)d_1^{n} + f_5(n)d_2^{n} + f_6(n)d_3^{n}}{f_1(n)c_1^{n} + f_2(n)c_2^{n} + f_3(n)c_3^{n}}$ $ = \sum_{i = 1}^{k}P_i(n)\frac {[Q_1(n),Q_2(n),...,Q_k(n)]}{Q_i(n)}r_i^{n} + O((1 - \epsilon_2)^n)$ $ T(n) = \sum_{i = 1}^{k}P_i(n)\frac {[Q_1(n),Q_2(n),...,Q_k(n)]}{Q_i(n)}r_i^{n}$ So exist $ k_1,k_2,...k_m \in Z$ such that $ k_1T(n + 1) + k_2T(n + 2) + ...... + k_mT(n + m) = 0$ And all roots of the characteristic equation are greater than or equal to 1. Then $ k_1(F(n + 1) - T(n + 1)) + k_2(F(n + 2) - T(n + 2)) + ...... + k_m(F(n + m) - T(n + m))$ $ = k_1F(n + 1) + k_2F(n + 2) + ...... + k_mF(n + m) \in Z$ And $ k_1(F(n + 1) - T(n + 1)) + k_2(F(n + 2) - T(n + 2)) + ...... + k_m(F(n + m) - T(n + m)) = O((1 - \epsilon_2)^n)$ So when $ n$ is sufficiently large $ k_1(F(n + 1) - T(n + 1)) + k_2(F(n + 2) - T(n + 2)) + ...... + k_m(F(n + m) - T(n + m)) = 0$ So $ F(n) - T(n)$ is a linear recurrence sequence which all roots of the characteristic equation are greater than or equal to 1. Since $ F(n) - T(n) = O((1 - \epsilon_2)^n)$ So $ F(n) - T(n) = 0$ Then $ \frac {f_4(n)d_1^{n} + f_5(n)d_2^{n} + f_6(n)d_3^{n}}{f_1(n)c_1^{n} + f_2(n)c_2^{n} + f_3(n)c_3^{n}}$ $ = \sum_{i = 1}^{k}\frac {P_i(n)}{Q_i(n)}r_i^{n}$ when $ n$ is sufficiently large

Hi my friend,thank you for your nice thought But I am a little confused about your notation,did you use $ \frac{y}{1+x}=y(1-x+x^2-x^3+...)$ to expand $ \frac{\frac{f_{4}(n)}{f_{1}(n)}(\frac{d_{1}}{c_{1}})^{n}+\frac{f_{5}(n)}{f_{1}(n)}(\frac{d_{2}}{c_{1}})^{n}+\frac{f_{6}(n)}{f_{1}(n)}(\frac{d_{3}}{c_{1}})^{n}}{1+\frac{f_{2}(n)}{f_{1}(n)}(\frac{c_{2}}{c_{1}})^{n}+\frac{f_{3}(n)}{f_{1}(n)}(\frac{c_{3}}{c_{1}})^{n}}$ then $ O((\frac{f_{2}(n)}{f_{1}(n)}(\frac{c_{2}}{c_{1}})^{n}+\frac{f_{3}(n)}{f_{1}(n)}(\frac{c_{3}}{c_{1}})^{n})^{2M+1}) )$ should be $ O((\frac{f_{2}(n)}{f_{1}(n)}(\frac{c_{2}}{c_{1}})^{n}+\frac{f_{3}(n)}{f_{1}(n)}(\frac{c_{3}}{c_{1}})^{n})^{2M+1}) )\times(\frac{f_{4}(n)}{f_{1}(n)}(\frac{d_{1}}{c_{1}})^{n}+\frac{f_{5}(n)}{f_{1}(n)}(\frac{d_{2}}{c_{1}})^{n}+\frac{f_{6}(n)}{f_{1}(n)}(\frac{d_{3}}{c_{1}})^{n})$ : Very sorry if I misunderstood you

Then $ O((\frac{f_{2}(n)}{f_{1}(n)}(\frac{c_{2}}{c_{1}})^{n}+\frac{f_{3}(n)}{f_{1}(n)}(\frac{c_{3}}{c_{1}})^{n})^{2M+1}) )\times(\frac{f_{4}(n)}{f_{1}(n)}(\frac{d_{1}}{c_{1}})^{n}+\frac{f_{5}(n)}{f_{1}(n)}(\frac{d_{2}}{c_{1}})^{n}+\frac{f_{6}(n)}{f_{1}(n)}(\frac{d_{3}}{c_{1}})^{n})$ $ =O((1-\epsilon)^{n})$ Why are you confused about it? :

Wow,thank you for your excellent first step!!! And could you please post the remaining steps? P.S Very sorry for my late reply,for I was very busy during the last two weeks

Here is a number-theoretic solution. Claim: We have $(a_1^k+a_2^k+a_3^k)(b_1^k-b_3^k) = (b_1^k+b_2^k+b_3^k)(a_1^k-a_3^k)$ for any $k\in\mathbb{Z}^+$. Proof: Let $T$ denote that expression. Take any prime $p > 2010(a_1^k+a_2^k+a_3^k)$ and by CRT, pick $n$ such that \begin{align*} n&\equiv k \pmod{p-1} \\ n&\equiv -\frac{a_1^k-a_3^k}{a_1^k+a_2^k+a_3^k} \pmod p \end{align*}Then by FLT we have $(n+1)a_1^n+na_2^n+(n-1)a_3^n \equiv n(a_1^k+a_2^k+a_3^k) + (a_1^k-a_3^k)\equiv 0\pmod p$. Thus \begin{align*} n(a_1^k+a_2^k+a_3^k) + (a_1^k-a_3^k) &\equiv 0\pmod p \\ n(b_1^k+b_2^k+b_3^k) + (b_1^k-b_3^k) &\equiv 0\pmod p \end{align*}Multiply the first equation by $(b_1^k+b_2^k+b_3^k)$ and subtract to $(a_1^k+a_2^k+a_3^k)$ times the second equation. We deduce that $p\mid T$ for any large prime $p$. Hence $T=0$. Back to the main problem. From the claim, we get $$(a_2b_1)^t+2(a_3b_1)^t+(a_3b_2)^t = (a_1b_2)^t+2(a_1b_3)^t+(a_2b_3)^t$$For any $t\in\mathbb{Z}^+$. This is enough to imply that $a_3b_1=a_1b_3$ and $\{a_2b_1, a_3b_2\} = \{a_1b_2, a_2b_3\}$. The latter imply $a_1b_2=a_2b_1$ and $a_3b_2=a_2b_3$. Thus let $a_i=ac_i$ and $b_i=bc_i$ where $\gcd(a,b)=1$. Plugging back, we deduce that $a\mid b$ so we are done.

Here is the analysis solution along the lines of user wrongthings. Let $$x_n = \frac{(n + 1)b_1^n + nb_2^n + (n - 1)b_3^n}{(n + 1)a_1^n + na_2^n + (n - 1)a_3^n}$$ The main claim is that there exists rational functions $t_1(n), \cdots, t_N(n)$ (fraction of the form $t_j(n)=\frac{P(n)}{Q(n)}$ ) and reals $q_1, \cdots, q_k$ at least 1 such that $x_n = \sum_{k=1}^N t_k(n) q_k^n$ for all sufficiently large $n$. Let $a= \max\{a_1, a_2, a_3\}$. Then for some rational functions $s_j(n)$, I can write this as $$x_n = \frac{s_1(n) (\frac{b_1}{a})^n + s_2(n) (\frac{b_2}{a})^n + s_3(n) (\frac{b_3}{a})^n}{1 + s_4(n) u^n + s_5(n) v^n}$$ Where $1,u,v$ is a permutation of $\frac{a_1}{a}, \frac{a_2}{a}, \frac{a_3}{a}$ I can rewrite $$x_n = \left( s_1(n) \left(\frac{b_1}{a}\right)^n + s_2(n) \left(\frac{b_2}{a}\right)^n + s_3(n) \left(\frac{b_3}{a}\right)^n \right) \left( \sum_{e\ge 0} \left( -s_4(n)u^n - s_5(n)v^n\right)^e\right) = \sum_{k\ge 1} r_k(n) q_k^n$$ Here $|q_j|$ is monotonically decreasing (The reordering of terms is due to absolute convergence.) Let's say $|q_{N+1}| < 1$. Let $f\colon \mathbb{R} \to [-1/2, 1/2)$ such that $f(x)\equiv x(\bmod\; 1)$. Then $$f\left( \sum_{k=1}^N r_k(n)q_k^n \right) = poly(n) q_{M+1}^n (1+o(1))$$ Let $P(n)$ such that $P(n)r_k(n)=Q_k(n) \in \mathbb{Z}[x]$ then $$f\left( \sum_{k=1}^N Q_k(n)q_k^n \right) = f\left( \sum_{k=1}^N P(n)r_k(n)q_k^n \right) = poly(n) q_{M+1}^n (1+o(1))\to 0$$ If $y_n = \sum_{k=1}^N Q_k(n)q_k^n$ then $y_n$ obeys some linear recursion of the form $\sum_{j=1}^T c_jy_{n+j}=0 \forall n$. It follows that $\sum_{j=1}^T c_jf(y_{n+j})=0 \forall n$ sufficiently large, since $|\sum_{j=1}^T c_jf(y_{n+j})|$ is an integer and is less than 1. It follows that $y_{n+j}$ also obeys a recursion with characteristic roots $r_1, \cdots, r_N$. In this case, $r_1, \cdots, r_N$ are all distinct positive rationals at least 1, so we can see that $f(y_{n+j})=k_1r_1^n +\cdots+k_Nr_N^n = 0$ for all sufficiently large $n$ (induct on $j$ to see $k_j=0$). This actually implies that $$x_n = \sum_{k=1}^N r_k(n)q_k^n$$ Now if I expand LHS (as functions without plugging $n$ in) in $$\sum_{k=1}^M s_k(n)p_k^n = \left(\sum_{k=1}^N r_k(n)q_k^n\right) \left((n + 1)a_1^n + na_2^n + (n - 1)a_3^n\right) = (n + 1)b_1^n + nb_2^n + (n - 1)b_3^n$$ (Where each $s_k(n)p_k^n$ is of the form $r_k(n) (n+2-j) (q_ka_j)^n$) We can see that since $$\sum_{k=1}^M s_k(n)p_k^n=(n + 1)b_1^n + nb_2^n + (n - 1)b_3^n$$holds for all sufficiently large $n$, they are actually the same function! Suppose $p_1 \ge \cdots \ge p_M$, then $p_1 = \max\{a_1,a_2,a_3\}q_1 = \max\{b_1,b_2,b_3\}p_M$, $p_3= \min\{a_1,a_2,a_3\}q_M=\min\{b_1,b_2,b_3\}$ because these are the only way to get $q_ka_j$ to be equal to $p_1, p_M$. We know from $$x_n = \left( \frac{n+1}{n+2-l} \left(\frac{b_1}{a}\right)^n + \frac{n}{n+2-l} \left(\frac{b_2}{a}\right)^n + \frac{n-1}{n+2-l} \left(\frac{b_3}{a}\right)^n \right) \left( \sum_{e\ge 0} \left( -s_4(n)u^n - s_5(n)v^n\right)^e\right) = \sum_{k\ge 1} r_k(n) q_k^n (\ast)$$that $r_N(n)$ is of the form $(n+2-l_1)^{c_1} (n+2-l_2)^{c_2} (n+2-l)^{-c_1-c_2}$ where $\{l_1,l_2\} = \{-1,0,1\} \backslash \{l\}$. Claim: If $l=\pi(1), a_{\pi(1)} > a_{\pi(2)} > a_{\pi(3)}$ then $b_{\pi(1)} > b_{\pi(2)} > b_{\pi(3)}$ Proof: From that expression it is easy to show that $r_1(n)=1$. The key claim is that $r_N(n)=1$ which implies the $(n+2-\pi(3))(a_{\pi(3)})^n$ gets multiplied by $1\times q_N^n$ to get $(n+2-\pi(3))(b_{\pi(3)})^n$ which implies $b_{\pi(3)}$ is minimum. Suppose $b_{\pi(3)}$ is not minimum, then $(n+2-\pi(3))(a_{\pi(3)})^n r_N(n) q_N^n = (n+2-\pi(2)) b_{\pi(2)}^n$. We know that all $r_N(n)$ is of the form $\frac{R(n)}{(n+2-\pi(1))^t}$. This implies that $t=0$ and $r_N(n)=1$ Claim: $a_{\pi(1)}b_{\pi(2)} = a_{\pi(2)}b_{\pi(1)}$ Proof: We know that $q_2 = \max \{ \frac{b_{\pi(2)}}{a_{\pi(1)}}, \frac{b_{\pi(1)}a_{\pi(2)}}{a_{\pi(1)}^2}\}$. If $a_{\pi(1)}b_{\pi(2)} \ne a_{\pi(2)}b_{\pi(1)}$ then it's clear that $\frac{b_{\pi(2)}}{a_{\pi(1)}} > \frac{b_{\pi(1)}a_{\pi(2)}}{a_{\pi(1)}^2}$ because otherwise there is one unique way to generate $R_j(n) (\frac{b_{\pi(1)}a_{\pi(2)}}{a_{\pi(1)}^2})^2 \in (b_{\pi(2)}, b_{\pi(1)})$ so this term doesn't get cancelled out. Therefore, $$b_{\pi(1)} = a_{\pi(1)} q_1, b_{\pi(2)} = a_{\pi(1)} q_2, b_{\pi(3)} = a_{\pi(3)} q_N, \frac{b_{\pi(2)}}{a_{\pi(1)}} > \frac{b_{\pi(1)}a_{\pi(2)}}{a_{\pi(1)}^2}$$ Note this implies that $a_{\pi(1)}q_2 \ne a_{\pi(2)}q_1$. Consider the third largest number among $a_kq_j$. There are two possibilities: $a_{\pi(2)}q_1$ and $a_{\pi(1)}q_3$. Their coefficients must cancel, but $l=\pi(1), a_{\pi(1)} > a_{\pi(2)} > a_{\pi(3)}$ then $b_{\pi(1)} > b_{\pi(2)} > b_{\pi(3)}$ gives contradiction. We can similarly show that $\frac{b_j}{a_j}$ is constant so we are done.

Trying to analyze MarkBcc168's solution for its motivation. Step 1: Applying a hard skill / well-known theorem. Well, clearly we need to simplify the expression given. Let's set \[(n+1)a_1^n+na_2^n+(n-1)a_3^n=n(a_1^n+a_2^n+a_3^n)+(a_1^n-a_3^n).\]Now we try to apply some more well-known theorems. If we commit to trying modulos/divisibility, then one of the most obvious theorems to use should be Fermat's Little Theorem (aka the theorem that reduces exponents for free). I think this is the most important step, trying to organize all the thoughts (since there's a lot to try) cohesively by applying specific steps and committing to something. We need to find a prime $p$ where \[p\mid n(a_1^n+a_2^n+a_3^n)+(a_1^n-a_3^n)\]and we can say $n\equiv k\pmod {p-1}$ which lets us write \[n(a_1^n+a_2^n+a_3^n)+(a_1^n-a_3^n)\equiv n(a_1^k+a_2^k+a_3^k)+(a_1^k-a_3^k)\equiv 0\pmod p\]hence we get the equivalence in MarkBcc168's solution. Step 2: Proving a result by bounding. I think this is probably a well-known hard skill: To prove $T=0$, it suffices to show $p\mid T$ for sufficiently large $p$. If you make heuristic estimates, you realize this has to be what you need to use (and you must coagulate your ideas into a solution path, or else you'll be confused and give up, rip). So we have that \[n(a_1^k+a_2^k+a_3^k)+(a_1^k-a_3^k)\equiv 0\pmod p\]\[n(b_1^k+b_2^k+b_3^k)+(b_1^k-b_3^k)\equiv 0\pmod p\]and the point now is that \[T=(a_1^k+a_2^k+a_3^k)(b_1^k-b_3^k)-(b_1^k+b_2^k+b_3^k)(a_1^k-a_3^k)\equiv 0\pmod p\implies T=0.\]Step 3: Finishing off. After this, there was an approach I tried where you realize that now \[a_1^n+a_2^n+a_3^n\mid b_1^n+b_2^n+b_3^n\]but this doesn't really generate traction. Let's commit to something else. Obviously, many terms in the expansion of $T$ should cancel, so expanding gives \[(a_2b_1)^k+2(a_3b_1)^k+(a_3b_2)^k=(a_1b_2)^k+2(a_1b_3)^k+(a_2b_3)^k.\]Looking at this equation, we just need to show that all the corresponding parts are actually equal, which seems obviously true. Oh wait, it is. We just need some asymptotics. Consider the maximum in $\{a_2b_1,a_3b_1,a_3b_2\}$ and $\{a_1b_2,a_1b_3,a_2b_3\}$. Evidently these are both equal. Notice that each of the six products has a coefficient $c\in \{1,2\}$ associated with it; we have two cases. If the coefficients assigned to the maximums are different, then we'll get, say $m=a_3b_1=a_1b_2=a_2b_3$. Then we trivially find $n=a_2b_1=a_3b_2=a_1b_3$, hence \[\frac{m}{n}=\frac{a_3}{a_2}=\frac{a_1}{a_3}=\frac{a_2}{a_1}\implies a_1=a_2=a_3,\]a contradiction. If the coefficients assigned to the maximums are the same, we can split into two subcases. When $c=2$, we get $a_3b_1=a_1b_3$ and by the condition on distinct integers it follows that $a_3b_2=a_2b_3,a_2b_1=a_1b_2$. This implies $b_i=ka_i$. When $c=1$, we can WLOG $a_2b_1=a_1b_2$, hence \[2(a_3b_1)^k+(a_3b_2)^k=2(a_1b_3)^k+(a_2b_3)^k\]now by the same maximum argument two numbers, one on each side, should be equal. We've already covered $a_3b_1=a_1b_3$, if $a_3b_1=a_2b_3$ or $a_1b_3=a_3b_2$ we'll obtain all four products equal, contradiction. All cases are exhausted and we may conclude.