1
$\begingroup$

Let $x_n$ and $y_n$ be sequences such that $x_0=y_0=1, x_1=y_1=13$ and $$x_{n+2}=38x_{n+1}-x_n,$$ $$y_{n+2}=20y_{n+1}-y_n$$ for $n\ge0$. I want to show that there is no common terms when $n\ge2$. In other words, there are no $n,m\ge2$ such that $x_n=y_m$.

I encountered this problem when tried to make an olympiad-like problem. So I am not sure it is true, but I have checked it with computer for $n\le10^{200000}$. (Since I am not a good coder, I can't make sure that it does not have an error such as overflow. Sorry...)

Is there any strategy to solve these kind of problems? If there is, and if you gave me just a hint or a related concept, I would be very happy! Thank you.

Edit:: I'll record what I already have tried before...

  • I calculated the exact formula through the characteristic polynomial, but I could not find something useful. What can I do with the roots, which seems to be just one of many ugly irrationals?

  • Taking modulo, in fact, allowed me to reduce a more complicated problem into this form(what I asked here). Even if modular arithmetic still can do something further, I have no idea. Which base would be appropriate?

  • This maybe TMI: the original problem was about simultaneous Pell's equation.

$\endgroup$
  • $\begingroup$ Induction seems like the logical first step to try... $\endgroup$ – 5xum Jul 18 '19 at 10:32
  • $\begingroup$ There is an explicit formula for $x_n$, $y_n$, as a linear combination of the roots of the characteristic polynomials of the linear recurrences, $P=\lambda^2-39\lambda+1$ (for $(x_n)$), and respectively $Q=\lambda^2-20\lambda+1$ (for $(y_n)$). One of the roots of $P,Q$ is in $(0,1)$, the other one in $(1,\infty)$. One can also consider the given recursions modulo some primes, then the values are obtained perodically, one can try to show that the periods are bigger and bigger for suitably chosen primes. $\endgroup$ – dan_fulea Jul 18 '19 at 10:59
  • $\begingroup$ @dan_fulea Would you tell me about growing periods with slightly more details? $\endgroup$ – user680089 Jul 18 '19 at 23:50
0
$\begingroup$

Yes, put $x_n=a^n$ to get $a^2-38a+1=0$ let $a_1$ and $a_2$ be the roots the $x_n=C_1 a_1^{n}+C_2 a_2^{n}$. you can calculate $C_1$ and $C_2$ from the conditions $x_0=0$ abd $x_1=13$. This method works if you get the $a$-equation which is free of $n$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.