Tübitak Lise 1. Aşama 2018 Soru 02

[Squidward]

$x_0, x_1, \dots , x_{2018}$ tam sayıları $x_0 = 1$, $ x_1 = 2$ ve her $ n \geq 1$ için $x_{n+1} = 3x_n - 2x_{n-1}$ koşullarını sağlıyorsa $x_{2018}$ sayısının $2018$ ile bölümünden kalan kaçtır?

$\textbf{a)}\ 0 \qquad\textbf{b)}\ 2  \qquad\textbf{c)}\ 4 \qquad\textbf{d)}\ 6 \qquad\textbf{e)}\ 8$

[Squidward]

Yanıt: $\boxed{C}$


$x_{n+1} = 3x_n - 2x_{n-1}$ koşullarını sağlayan bir dizideki terimler arasındaki fark her terimde $2$ kat artar, böylece $x_2 = 4, x_3 = 8, x_4 = 16$ olduğu görülür ve her terim $x_n = 2^n$ koşulunu sağlar, ilk birkaç terim yazılarak tahmin de edilebilir, $2018.$ terim $2^{2018}$ olur.

$2018 = 2 \cdot 1009$ ve $ 2 | 2^{2018} $ olduğundan sadece $\mod 1009$ da incelememiz yeterlidir. Fermat'ın Küçük Teoreminden $2^{1008} \equiv 1 \pmod {1009} $ ve $2^{2018} \equiv 2^{1008} \cdot 2^{1008} \cdot 2^2 \equiv 1 \cdot 1 \cdot 2^2 \equiv 4 \pmod {1009}$. Yani kalan $4$ tür.

[Lokman Gökçe]

Yanıt: $\boxed{C}$

İndirgemeli dizi yardımıyla soruyu çözelim. $x_{n+1} = 3x_n - 2x_{n-1}$ doğrusal indirgemeli dizisinin karakteristik polinomu $r^2-3r+2=0$ olup kökleri $r_1=1$ ve $r_2=2$ dir. Dolayısıyla genel terim $x_n= A\cdot 2^2 + B\cdot 1^n$ formundadır.

$n=0$ için $x_0=A+B=1$
$n=1$ için $x_1=2A+B=2$

denklemlerinden $A=1$ ve $B=0$ bulunur. Dolayısıyla $x_n=2^n$ elde edilir. Bu aşamadan sonra $x_{2018}=2^{2018}$ sayısının $2018$ ile bölümünden kalanı ilk çözümde olduğu gibi $4$ olarak bulabiliriz.