Problem B. 4005. (May 2007)
B. 4005. For every positive integer n, let an denote the number of ways n is obtained as a sum of terms that are all 1, 3 or 4. The order of the terms also matters. Prove that a2006a2007a2008 is a perfect cube.
(4 pont)
Deadline expired on June 15, 2007.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás: Az értelemszerű a0=1 jelölést is bevezetve, a1=a2=1, a3=2, n
4 esetén pedig a szóba jövő összegeket aszerint csoportosítva, hogy az utolsó tag 1,3, vagy pedig 4, az an=an-1+an-3+an-4 rekurzív összefüggést írhatjuk fel, aminek alapján a sorozat néhány további eleme a4=4, a5=6, a6=9, a7=15, a8=25, a9=40, a10=64, a11=104, a12=169. Látható, hogy a sorozat minden második eleme négyzetszám, méghozzá a2n=Fn2, ahol Fn az F0=F1=1, Fn=Fn-1+Fn-2 (n2) rekurzióval definiálható Fibonacci-féle sorozat. Innen pedig az a2n+1=Fn+1Fn összefüggést is felfedezhetjük.
Ezeket az észrevételeket teljes indukcióval könnyen igazolhatjuk. Ha már 0-tól n-ig igazoltuk mind a két összefüggést akkor az indukciós lépés így végezhető el:
a2n+2=a2n+1+a2n-1+a2n-2=Fn+1Fn+FnFn-1+Fn-12=
=Fn+1Fn+(Fn+Fn-1)Fn-1=Fn+1Fn+Fn+1Fn-1=Fn+12,
illetve
a2n+3=a2n+2+a2n+a2n-1=Fn+12+Fn2+FnFn-1=
=Fn+12+Fn(Fn+Fn-1)=Fn+12+FnFn+1=Fn+2Fn+1.
Ezek alapján minden n természetes számra
a2na2n+1a2n+2=Fn2(FnFn+1)Fn+12=(FnFn+1)3=a2n+13,
ami n=1003 esetén igazolja az állítást.
Statistics:
44 students sent a solution. 4 points: Aczél Gergely, Ágoston Tamás, Blázsik Zoltán, Bodor Bertalan, Cseh Ágnes, Cserép Máté, Csuvár Andrea, Éles András, Farkas Márton, Fonyó Dávid, Grósz Dániel, Honner Balázs, Kiss 243 Réka, Korom-Vellás Judit, Kunos Ádám, Kunovszki Péter, Mihálykó Ágnes, Nagy 314 Dániel, Nagy 648 Donát, Peregi Tamás, Salát Zsófia, Sümegi Károly, Szabó 895 Dávid, Szalkai Balázs, Szűcs Gergely, Tossenberger Anna, Tóth 666 László Márton, Varga 171 László, Wagner Zsolt, Wolosz János. 3 points: Almási 270 Gábor András, Aujeszky Tamás, Dékány Tamás, Dinh Hoangthanh Attila, Keresztfalvi Tibor, Konkoly Csaba. 2 points: 1 student. 1 point: 1 student. 0 point: 3 students. Unfair, not evaluated: 3 solutionss.
Problems in Mathematics of KöMaL, May 2007