Tübitak Lise 1. Aşama 1997 Soru 09

[geo]

$(a_n)_{n = 1}^{\infty}$ tamsayı dizisi, $a_1\equiv 1 \pmod {13}$, $a_2 \equiv 4 \pmod {13}$ ve $n \geq 3$ için, $a_n=4a_{n-1}-4a_{n-2} \pmod {13}$ koşulunu sağlıyorsa, $a_{100} \pmod {13}$ aşağıdakilerden hangisidir?

$
\textbf{a)}\ 7
\qquad\textbf{b)}\ 6
\qquad\textbf{c)}\ 12
\qquad\textbf{d)}\ 9
\qquad\textbf{e)}\ \text{Hiçbiri}
$

[geo]

Yanıt: $\boxed{A}$

$a_1 = 1$,
$a_2 = 4$,
$a_3 = 4\cdot 3 = 3\cdot 2^2$,
$a_4 = 4 \cdot (3\cdot 2^2 - 4) =  4\cdot 2^3$
$a_5 = 4 \cdot (4 \cdot 2^3 - 3 \cdot 2^2) = 5 \cdot 2^4$

İddia: $a_n = n\cdot 2^{n-1}$

$\begin{array}{lcl}
a_{n+1} &=& 4(a_n - a_{n-1}) \\
& = & 4(n\cdot 2^{n-1} - (n-1)\cdot 2^{n-2}) \\
& = & 4(n\cdot (2^{n-1} - 2^{n-2}) + 2^{n-2} ) \\
& = & 4(n\cdot 2^{n-2} + 2^{n-2}) \\
& = & 4(n+1)2^{n-2} \\
& = & (n+1)2^{n} \quad \blacksquare
\end{array}
$

Soruya geri dönersek,
$$a_{100} = 100 \cdot 2^{99}$$ olacaktır.
Fermat'ın Küçük Teoreminden $$a^{12} \equiv 1 \pmod {13}$$
$$\begin{array}{lcll}
a_{100} & \equiv & 100 \cdot 2^{99} & \pmod {13} \\
& \equiv & 9 \cdot 2^{96} \cdot 2^3 & \pmod {13} \\
& \equiv & 72 & \pmod {13} \\
& \equiv & 7 & \pmod {13} \\

\end{array}
$$

[geo]

Doğrusal indirgemeli dizilerin çözüm yöntemini uygulayacağız.

$a_n = r^2$, $a_{n-1} = r$, $a_{n-2} = 1$ olarak aldığımızda, $$r^2 = 4r - 4 \Rightarrow (r-2)^2 = 0 \Rightarrow r_{1,2} = 2$$
Bu durumda genel terim $$a_n = a\cdot 2^n + b\cdot n\cdot 2^{n}$$ şeklinde olacaktır.
$a_1 = 2a + 2b = 1$ ve $a_2 = 4a + 8b = 4$ denklemlerinin ortak çözümünden $a=0$ ve $b=\dfrac 12$ gelecektir. O halde genel terim $$a_n = n\cdot 2^{n-1}$$ olacaktır.
$a_{100} = 100 \cdot 2^{99}$ elde edilir. Fermat'ın Küçük Teoreminden faydalanarak ya da $2^6 \equiv 64 \equiv -1 \pmod {13}$ olduğu fark edilerek $a_{100} \equiv 7 \pmod {13}$ sonucuna ulaşılabilir.

[geo]

Bir nevi doğrusal indirgemeli dizilerin çözüm yönteminin ispatını yaparak sonuca gitmeye çalışalım.
$$a_n = 4a_{n-1} - 4a_{n-2}$$
Her tarafı $2^n$ ile bölelim.
$$\dfrac {a_n}{2^n} = 2\cdot \dfrac{a_{n-1}}{2^{n-1}} - \dfrac{a_{n-2}}{2^{n-2}} \tag{1}$$

$b_n = \dfrac {a_n}{2^n}$ dizisini tanımlayalım. $b_1 = \dfrac 12$ ve $b_2 = 1$ olacaktır. $(1)$ deki eşitliği $b_n$ cinsinden yazarsak
$$b_n = 2b_{n-1} - b_{n-2} \tag {2}$$ elde edilir. Biraz düzenlemeyle $$b_n  - b_{n-1}= b_{n-1} - b_{n-2} \tag{3}$$ elde edilir. Tüm ardışık terimlerin farkı birbirine eşit olduğu için $b_n$ dizisi aritmetik dizidir. $$b_n - b_{n-1} = b_2 - b_1 = \dfrac 12 \tag{4}$$ $b_n$ genel terimini
$$b_n = (n-1)\cdot \dfrac 12 + b_1 = \dfrac n2 \tag {5}$$ şeklinde elde ederiz. Bu durumda $a_n$ dizisi, $$a_n = 2^n b_n = 2^n\cdot \dfrac n2 =n2^{n-1} \tag{6}$$ olarak elde edilir.
Fermat'ın Küçük Teoreminden
$$a_{100} \equiv 100 \cdot 2^{99} \equiv 9 \cdot (2^{12})^8 \cdot 2^3 \equiv 72 \equiv 7 \pmod {13}$$ elde edilir.