The sequences $\{u_{n}\}$ and $\{v_{n}\}$ are defined by $u_{0} =u_{1} =1$ ,$u_{n}=2u_{n-1}-3u_{n-2}$ $(n\geq2)$ , $v_{0} =a, v_{1} =b , v_{2}=c$ ,$v_{n}=v_{n-1}-3v_{n-2}+27v_{n-3}$ $(n\geq3)$. There exists a positive integer $N$ such that when $n> N$, we have $u_{n}\mid v_{n}$ . Prove that $3a=2b+c$.
Problem
Source: China Changsha ,Dec 23, 2016
Tags: algebra, number theory, Sequence
23.11.2016 12:18
23.11.2016 12:37
Aiscrim wrote:
Powerful. Thanks.
23.11.2016 14:51
Aiscrim wrote: As $v_1\in \mathbb{Z}$, we infer $\beta=\gamma$. You have to be careful here. It is possible that $\alpha$ is not rational and so $\beta = \gamma$ is not immediate, though I think a little more work would suffice to show that fact.
27.11.2016 09:33
Two questions: 1) Are $a, b, c$ integers? Positive integers? 2) Is the $u_{n-2}$ a typo in the $v_n$ definition? Should it be $v_{n-2}$?
27.11.2016 11:38
$v_{n}=v_{n-1}-3v_{n-2}+27v_{n-3}$ $(n\geq3)$
27.11.2016 19:49
sqing wrote: $v_{n}=v_{n-1}-3v_{n-2}+27v_{n-3}$ $(n\geq3)$ Thank you. And are $a, b, c$ integers?
27.11.2016 20:46
The key is to realise what connects the two given recurrence relations. Note that if $\alpha,\beta$ are the roots of $x^2-2x+3=0$, then $\alpha^2,\beta^2,\alpha\beta$ are the roots of $x^3-x^2+3x-27=0$. Hence, for any two sequences $\{a_n\},\{b_n\}$ satisfying the recurrence relation of $\{u_n\}$, then $\{a_nb_n\}$ must satisfy the recurrence relation of $v_n$. Hence in particular, we wish to define $\{w_n\}$, satisfying the same recurrence relation as $\{u_n\}$, such that $\{v_n-(u_n\cdot w_n)\}$ (which still satisfies the recurrence relation of $v_n$) has its $3^n$ term isolated. Now we balance the coefficients: let the first three terms be $\lambda,3\lambda,9\lambda$, thus the first three terms of $\{w_n\}$ are $a-\lambda, b-3\lambda,9\lambda -c$, and checking the original relation we get $9\lambda - c = 2(b-3\lambda) - 3(a-\lambda)$, or $\lambda = \frac{2b+c-3a}{12}$. Since $v_n$ are integers for all sufficiently large $n$, $a,b,c$ must be rational, so the first two terms of $w_n$ are rational too, so let $k\in \mathbb{N}$ be such that $kw_n$ are all integers. then $u_n | k\lambda \cdot 3^n$ for all sufficiently large $n$, but $u_n$ is unbounded and not divisible by 3, so $\lambda = 0$.
01.12.2016 07:18
ethical_man wrote: sqing wrote: $v_{n}=v_{n-1}-3v_{n-2}+27v_{n-3}$ $(n\geq3)$ Thank you. And are $a, b, c$ integers? Just confirmed that $a, b, c$ are not necessarily integers, found by checking this site: http://www.zyymat.com/chinese-mathematical-olympiad-cmo-2017.html.
01.12.2016 10:12
The trick is to show that even if $a, b, c$ are not integers, since $v_n$ is EVENTUALLY AN INTEGER which is to be divisible by $u_n$ from some point, we can use that to show that $a, b, c$ are cleaner than we think it is ($a, b, c$ are just REALS; didn't say anything about rational or integer) As Aiscrim's solution suggested let $p = 1 + \sqrt{-2}, q = 1 - \sqrt{-2}$ then $u_n = \frac{p^n + q^n}{2}$ and notice that $v_n$'s characteristic equation's solutions are $3, p^2,$ and $q^2$ thus, $v_n = A \times p^{2n} + B\times q^{2n} + C \times 3^n$ for some real $A, B,$ and $C$ for future reference, let $v'_n = v_{n+N}$ $A' = A \times p^{2N}$ $B' = B \times q^{2N}$ $C' = C \times 3^N$ then clearly $v'_n = A' \times p^{2n} + B' \times q^{2n} + C' \times 3^n$ Consider the set $\noindent \mathbb{Q}' = \mathbb{Q}\left(\sqrt{-2} \right) = \{ a + b \sqrt{-2} \, | \, a, b \text{ are rationals } \} \text{ and } \mathbb{Z}' = \mathbb{Z}\left(\sqrt{-2}\right) = \{ a + b \sqrt{-2} \, | \, a, b \text{ are integers } \}$ then $\mathbb{Q}'$ is closed under $+, -, \times, \div$ notice that p, q are elements of $\mathbb{Z}'$ Claim $1: \, A, B$ are elements of $\mathbb{Q}'$, and $A, B$ are conjugates pf. We need to be careful because $v_0, v_1, v_2$ are not necessarily integers, but we do know for sure that $v'_0, v'_1,$ and $v'_2$ are integers We have $v'_0 = A' + B' + C'$ $v'_1 = A'\times p^2 + B'\times q^2 + 3C'$ $v'_2 = A'\times p^4 + B'\times q^4 + 9C'$ After intense bashing, we arrive at the fact that $A'$ and $B'$ are conjugate elements of $\mathbb{Q}'$ and $C'$ is rational <APPARENTLY YOU CAN ALSO SAY : the solutions of the linear simultaneous equations regarding $\mathbb{Q}'$ must also be in $\mathbb{Q}'$ as $\mathbb{Q}'$ is a ring> Since $A' = A \times p^{2N}, B' = B \times q^{2N}, C' = C \times 3^N$ $A$ and $B$ are also conjugate elements of $\mathbb{Q}'$ and $C$ remains a rational. $\mathcal{Q.E.D.}$ Now, consider the following sequence $l_n = \frac{v_n}{u_n} = 2\left(A \times p^n + B \times q^n + \frac{(C-A-B)3^n}{p^n + q^n}\right)$ notice that $(pq)^n = 3^n$ It's pretty clear that $A \times p^n + B \times q^n$ is rational by itself, and $\frac{(C-A-B)3^n}{p^n + q^n}$ is also rational. If $l_n$ is an integer, then we want these two rationals to magically have a similar denominator so that they match up to be an integer perfectly. Claim $2: \, 3 \nmid u_n$ pf. this is quite trivial as $u_n = -u_{n-1}$ and $u_0 \equiv 1 \mod{3}$ $\mathcal{Q.E.D.}$ Define $f:\mathbb{Q}' \mapsto \mathbb{N}$ such that for some element $x$ of $\mathbb{Q}'$, we have $f(x) =$ the smallest positive integer such that $x \times f(x)$ is an element of $\mathbb{Z}'$ so, pretty much the l.c.m of the denominator of the real part and the integer part Claim $3: \, f(A\times p^n) \ge f(A\times p^{n+1}), f(B\times q^n) \ge f(B\times q^{n+1})$ pf. Trivial as $p, q$ are elements of $\mathbb{Z}'$, which does not affect the denominator at all, or at the least, cancels stuff out and makes it smaller Claim $4: \, p_n + q_n \to \infty$ when $n \to \infty$ pf. Since $|p| = \sqrt{3} > 1$, it must diverge. and since $p, q$ are conjugates, we have $p_n + q_n$ is an integer. $\mathcal{Q. E. D.}$ Thus, since the denominator of $\frac{(C-A-B)3^n}{p^n + q^n}$ explodes, while $A\times p^n + B\times q^n$ does not, $l_n$ cannot be an integer unless $C - A - B = 0$ Thus, $C - A - B = 0$ coming back to $v_n$, sub in $C = A + B$ then when you sub it into $v_0, v_1, v_2$, everything works out and we're done! $a = 2(A+B)$ $b = (2+2\sqrt{-2})A + (2-2\sqrt{-2})B$ $c = (2-4\sqrt{-2})A + (2+\sqrt{-2})B$ so $3a = 2b + c = 6(A+B)$ $\mathcal{Q. E. D.}$ A more formal proof of Claim $4$: let $p = \sqrt{3} e^{i \theta}$. then $q = \sqrt{3}e^{-i \theta}$ and clearly $\theta \neq 0, \pi$ then $p^n + q^n = (2\sqrt{3})^n \cos{(n\theta)}$ and since $n\theta$ is linear, it will never be the case that $\cos{(n\theta)}$ will tend to $0$ and since $(\sqrt{3})^n$ blows up, the whole sequence blows up!
06.12.2016 03:13
fattypiggy123 wrote: Aiscrim wrote: As $v_1\in \mathbb{Z}$, we infer $\beta=\gamma$. You have to be careful here. It is possible that $\alpha$ is not rational and so $\beta = \gamma$ is not immediate, though I think a little more work would suffice to show that fact. Sorry, but just not clear on one thing: If $\beta = \gamma$, then that would imply that $$v_n=\alpha\cdot 3^n+\beta \cdot \left (-1-2i\sqrt{2} \right )^n+\beta \cdot \left (-1+2i\sqrt{2} \right )^n$$i.e. $a = v_0 = \alpha+2\beta$, $b = v_1 = \alpha-2\beta$, and $c = v_2 = \alpha-14\beta$, so three equations with only two variables, which means there is some equation between $a, b, c$, but that is false since $a, b, c$ are arbitrary, independent to each other... Thanks!