1996 Antalya Matematik Olimpiyatı 2. Aşama Soru 2

[matematikolimpiyati]

$u_1=1,\ u_2=1$ ve her $k \geq 1$ için $u_{k+2}=u_k+u_{k+1}$ olarak tanımlanan $(u_n)$ dizisi Fibonacci dizisi olarak bilinir. Her $k \geq 1$ için $u_{5k}$'nın $5$ ile tam bölündüğünü gösteriniz.

[Metin Can Aydemir]

$k=1$ için $u_5=5$ olduğundan iddia doğrudur. Şimdi $k=n$ için iddianın doğru olduğunu kabul edelim. $$u_{5(n+1)}=u_{5n+5}=u_{5n+4}+u_{5n+3}=2u_{5n+3}+u_{5n+2}$$ $$=3u_{5n+2}+2u_{5n+1}=5u_{5n+1}+3u_{5n}$$ olacaktır. Kabul gereği $5\mid u_{5n}$ olduğundan $5\mid (5u_{5n+1}+3u_{5n})$ ve $5\mid u_{5n+5}$ olacaktır. Dolayısıyla iddia $k=n+1$ için de doğrudur. Tümevarımdan, her $k\geq 1$ için doğrudur.