A C. 997. feladat (2009. szeptember)

C. 997. Bizonyítsuk be, hogy a Fibonacci-sorozat minden negyedik tagja osztható 3-mal. (A Fibonacci-sorozatban a₁=1, a₂=1 és a_n=a_n-1+a_n-2 minden , n3 esetén.)

(5 pont)

A beküldési határidő 2009. október 12-én LEJÁRT.

Megoldás. Bizonyítás teljes indukcióval: $\displaystyle a_4=3$ ami osztható $\displaystyle 3$-mal. Minden negyedik sorozat-elem sorszáma $\displaystyle 4$-gyel osztható, azaz az $\displaystyle a_{4k}$ tagokról szól a feladat. Tegyük fel, hogy minden $\displaystyle k<n$-re $\displaystyle 3\mid a_{4k}.$

$\displaystyle a_{4(n+1)}=a_{4n+3}+a_{4n+2}=a_{4n+2}+a_{4n+1}+a_{4n+2}=2(a_{4n}+a_{4n+1})+a_{4n+1}=2a_{4n}+3a_{4n+1}$

a sorozat definícióját háromszor alkalmazva. Ezek szerint a következő negyedik tag egy hárommal osztható (az indukciós feltevés szerint) és egy másik háromszorosa összegeként kapható meg, amiből következik, hogy maga is osztható 3-mal.

Statisztika:

435 dolgozat érkezett.
5 pontot kapott:	210 versenyző.
4 pontot kapott:	72 versenyző.
3 pontot kapott:	93 versenyző.
2 pontot kapott:	42 versenyző.
1 pontot kapott:	12 versenyző.
0 pontot kapott:	2 versenyző.
Nem versenyszerű:	4 dolgozat.

A KöMaL 2009. szeptemberi matematika feladatai