Let $ \{X_n\}$ and $ \{Y_n\}$ denote two sequences of integers defined as follows: \begin{align*} X_0 = 1,\ X_1 = 1,\ X_{n + 1} = X_n + 2X_{n - 1} \quad (n = 1,2,3,\ldots), \\ Y_0 = 1,\ Y_1 = 7,\ Y_{n + 1} = 2Y_n + 3Y_{n - 1} \quad (n = 1,2,3,\ldots).\end{align*}Prove that, except for the "1", there is no term which occurs in both sequences.
Problem
Source: USAMO 1973
Tags: modular arithmetic
ocha
07.03.2010 03:49
Assuming you actually mean $ X_{n+1}=X_n + 2X_{n-1}$ and the same for $ Y_n$ then, taking the sequences $ \mod 8$ $ \{X_i\} = \{1,1,3, - 3,3, - 3,3,...\}$ $ \{Y_i\} = \{1, - 1,1, - 1,1, - 1,...\}$
Brut3Forc3
07.03.2010 04:25
ocha wrote: Assuming you actually mean $ X_{n + 1} = X_n + 2X_{n - 1}$ and the same for $ Y_n$ then, taking the sequences $ \mod 8$ $ \{X_i\} = \{1,1,3, - 3,3, - 3,3,...\}$ $ \{Y_i\} = \{1, - 1,1, - 1,1, - 1,...\}$ Yes, it was a typo. My bad. How does this finish the problem?
ocha
07.03.2010 04:50
Brut3Forc3 wrote: How does this finish the problem? if $ X_a=Y_b$ then we would have $ \pm 3\equiv \pm 1 \mod 8$...
Brut3Forc3
07.03.2010 04:56
Oh. I think I misread it and thought that your sets repeated (the whole pattern, not just the plus minus 3 only), but now I get what you mean.
tc1729
14.05.2012 03:27
Solving the first recurrence yields \[x_n=X(-1)^n+Y2^n.\] Using $x_1$ and $x_2$ yields \[x_n=\frac{2^n+(-1)^{n+1}}{3}.\] Similarly, solving for the second recurrence yields \[y_n=2\cdot 3^{n-1}+(-1)^n.\] So if $x_m=y_n$ then $2\cdot 3^n+3(-1)^n=2^m+(-1)^{m+1}$ or $2\cdot 3^n+3(-1)^n+(-1)^m$. If $m=1$ or $2$, then $n=1$ is the only solution, corresponding the the fact that the term $1$ is in both sequences. If $m>2$, then $2^m\equiv 0\pmod 8$. But we have $3^n\equiv (-1)^n\pmod 4$, so \[2\cdot 3^n+3(-1)^n+(-1)^m\equiv 5(-1)^n+(-1)^m\pmod 8\] which cannot be $0\mod 8$. Hence there are no solutions for $m>2$, and the only integer in both sequences is indeed $1$. $\Box$
OlympusHero
12.04.2021 06:42
This is probably overkill, but I still like it
We convert to explicit form. The first recursion can be expressed in the form $X_n=A(2)^n + B (-1)^n$, so $1=A+B$ and $1=2A-B$, or $A=\frac{2}{3}$, $B=\frac{1}{3}$. The explicit form is therefore $X_n=\frac{2}{3}(2^n)+\frac{1}{3}(-1)^n$. Similarly, we express the second recursion in the form $Y_n=C(3^n)+D(-1)^n$, so $1=C+D$, $7=3C-D$ or $A=2$, $B=-1$. The explicit form is therefore $2(3^n)-1(-1)^n$. Equating these and simplifying, we obtain $3^{n+1}=2(-1)^n+2^n$. Via simple bounding, we always have $2(-1)^n+2^n < 3^{n+1}$ if $n>0$, meaning that there is no term apart from the $1$ that appears in both sequences. $\blacksquare$
jred
03.06.2021 11:04
OlympusHero wrote: This is probably overkill, but I still like it
We convert to explicit form. The first recursion can be expressed in the form $X_n=A(2)^n + B (-1)^n$, so $1=A+B$ and $1=2A-B$, or $A=\frac{2}{3}$, $B=\frac{1}{3}$. The explicit form is therefore $X_n=\frac{2}{3}(2^n)+\frac{1}{3}(-1)^n$. Similarly, we express the second recursion in the form $Y_n=C(3^n)+D(-1)^n$, so $1=C+D$, $7=3C-D$ or $A=2$, $B=-1$. The explicit form is therefore $2(3^n)-1(-1)^n$. Equating these and simplifying, we obtain $3^{n+1}=2(-1)^n+2^n$. Via simple bounding, we always have $2(-1)^n+2^n < 3^{n+1}$ if $n>0$, meaning that there is no term apart from the $1$ that appears in both sequences. $\blacksquare$
But you just proved that $X_n$ cannot be equal to $Y_n$.
wateringanddrowned
03.06.2021 11:45
I really want to know how to proof a more general case,what if characteristic roots are irrational?(in this case,someone told me if the sequence is different,they had only finite terms which occur in both sequences.)
lifeismathematics
25.07.2022 16:38
so $x_{n+1}=x_{n}+2x_{n-1}$. Set $x_{n}=p\cdot \alpha^{n}+q\cdot \beta^{n}$ where $\alpha$ and $\beta$ are roots of the equation $t^2-t-2=0$. So by $x_{0}=1$ and $x_{1}=1$ we get $p=\frac{2}{3},q=\frac{1}{3}$. So we get $x_{n}=\frac{2^{n+1}+(-1)^{n}}{3}$. Similarly we set $y_{n}=a\cdot (\gamma)^n+b\cdot (\delta)^{n}$ we get $y_{n}=2\cdot 3^{n}+(-1)^{n+1}$. Now let's sew for any $i,j$ if $
x_{i}=y_{j}$ , so we get $2^{i+1}+(-1)^{i}=2\cdot 3^{j+1}+3\cdot (-1)^{j+1}$.for $i,j>2$
taking $mod 9$ we get $(-1)^{i-2}+(-1)^{i} \equiv 3(-1)^{j+1} (mod 9)$ which is not true hence , sequence $\{x_{n}\}$ and $\{y_{n}\}$ shares no common numbers other than $1.$
huashiliao2020
13.04.2023 05:34
jred wrote: OlympusHero wrote: This is probably overkill, but I still like it
We convert to explicit form. The first recursion can be expressed in the form $X_n=A(2)^n + B (-1)^n$, so $1=A+B$ and $1=2A-B$, or $A=\frac{2}{3}$, $B=\frac{1}{3}$. The explicit form is therefore $X_n=\frac{2}{3}(2^n)+\frac{1}{3}(-1)^n$. Similarly, we express the second recursion in the form $Y_n=C(3^n)+D(-1)^n$, so $1=C+D$, $7=3C-D$ or $A=2$, $B=-1$. The explicit form is therefore $2(3^n)-1(-1)^n$. Equating these and simplifying, we obtain $3^{n+1}=2(-1)^n+2^n$. Via simple bounding, we always have $2(-1)^n+2^n < 3^{n+1}$ if $n>0$, meaning that there is no term apart from the $1$ that appears in both sequences. $\blacksquare$
But you just proved that $X_n$ cannot be equal to $Y_n$. Yes, that is what we are trying to prove. Back to the problem. We can prove this by induction. Base Case: Y_1>X_1, Y_2=2x7+3x1=17>3=1+2x1=X_2. Now suppose this is true for some k. Since Y_k>X_k, 2Y_k>X_k, and 3Y_(k-1)>2X_(k-1), so adding these two gives Y_(k+1)>X_(k+1), which means Y_n will always be greater than X_n for all $n\geq1$. Also, can someone tell me the latex for putting a black/white square at the end of your proofs? Thanks @below and @2below.
cinnamon_e
13.04.2023 05:38
white square is \square and black square is \blacksquare
S.Das93
13.04.2023 05:41
huashiliao2020 wrote: Yes, that is what we are trying to prove. Back to the problem. We can prove this by induction. Base Case: $Y_1>X_1, Y_2=2\cdot7+3\cdot1=17>3=1+2\cdot1=X_2$. Now suppose this is true for some $k$. Since $Y_k>X_k, 2Y_k>X_k$, and $3Y_{k-1}>2X_{k-1}$, so adding these two gives $Y_{k+1}>X_{k+1}$, which means $Y_n$ will always be greater than $X_n$ for all $n\geq1$. $\blacksquare$ Also, can someone tell me the latex for putting a black/white square at the end of your proofs?