disjuncte rijen
Opgave - USAMO 1973 vraag 2
We definiëren $a_n$ door $a_1=a_2=1$ en $a_{n+2}=a_{n+1}+2a_n$, en $b_n$ door $b_1=1,b_2=7$ en $b_{n+2}=2b_{n+1}+3b_n$. Toon aan dat enkel het getal 1 in beide rijen voorkomt.
- login om te reageren
Olympia
Nederlandstalig olympiadeproject
Zoeken
Random generator
Niveau
Wie is online
Er zijn momenteel 0 gebruikers en 2 gasten online.
Oplossing
Eerste gedacht is gewoon expliciet $a_n = (2^n - (-1)^n)/3$ en $b_n = 2\cdot 3^{n-1} + (-1)^n$ te vinden en dan gelijkstellen: $2^n = 2\cdot 3^n + 4\cdot (-1)^n$. Modulo 4 zegt dan $n \leq 1$, dus $n = 1$.
Edit: iets over het hoofd gezien: de gelijke termen moeten niet op dezelfde plaats in de rij voorkomen natuurlij :smile: Maar stel dus $a_n = b_m$. Dan is $2^n = 2\cdot 3^m + 3\cdot(-1)^m + (-1)^n$.
Voor $n = 1$ krijgen we $1 = 2\cdot 3^{m-1} + (-1)^m$, en dus $m = 1$ na een snelle controle.
Voor $n = 2$ is dan $1 = 2\cdot 3^m + 3\cdot (-1)^m$. Modulo 3 zegt dat dit niet kan voor $m>0$.
Stel nu $n\geq 3$. Dan is $8 | 2^n$. Dan moet dus $0 \equiv 2\cdot 3^m + 3\cdot(-1)^m + (-1)^n \equiv 5\cdot (-1)^m + (-1)^n\pmod{8}$, en dat kan niet.
Lijkt me idd de goeie aanpak, alleen zie ik niet waarom (en zelfs hoe?) je die expliciete vorm berekent, ik ging iets gelijkaardigs doen met de recursie zelf: voor $n\ge3$ is
$$\begin{array}{rccll}a_n&\equiv& 4+(-1)^n &\in\{3,5\}&\pmod{8}\\b_n&\equiv& -(-1)^n &\in\{1,7\}&\pmod{8}\end{array}$$
per inductie. De inductiestap volgt direct door deze uitdrukking in te vullen in de gegeven recursiebetrekkingen.