A B. 4640. feladat (2014. május)

B. 4640. Számítsuk ki a

\(\displaystyle \sum_{j=0}^{n} \binom{2n}{2j} {(-3)}^{j} \)

összeget.

(5 pont)

A beküldési határidő 2014. június 10-én LEJÁRT.

Megoldás. Legyen

\(\displaystyle S_m=\sum_{j=0}^{[m/2]} \binom{m}{2j}{(-3)}^j. \)

Azt állítjuk, hogy \(\displaystyle S_{2n}\) értéke \(\displaystyle 2^{2n}\), ha \(\displaystyle n\) osztható 3-mal, és \(\displaystyle -2^{2n-1}\) különben. Az állítást \(\displaystyle n\)-re vonatkozó teljes indukcióval bizonyítjuk. Az \(\displaystyle n=1,2,3\) esetekben könnyen ellenőrizhető, hogy valóban teljesül:

\(\displaystyle S_2=1-3\cdot1=-2,\quad S_4=1-3\cdot 6+9\cdot 1=-8,\quad S_6=1-3\cdot15+9\cdot15-27\cdot1=64. \)

Az indukcióhoz elég megmutatni, hogy \(\displaystyle m>3\) esetén \(\displaystyle S_m=(-8)S_{m-3}\), hiszen ebből \(\displaystyle S_{2n}=(-8)S_{2n-3}=64S_{2(n-3)}\), amiből már azonnal következik az állítás. Az \(\displaystyle S_m=(-8)S_{m-3}\) összefüggés igazolásához először az \(\displaystyle \binom{m}{2k}\) binomiális együtthatót írjuk fel a Pascal-háromszög \(\displaystyle (m-3)\)-adik sorában lévő binomiális együtthatók összegeként:

\(\displaystyle \binom{m}{2j}=\binom{m-1}{2j-1}+\binom{m-1}{2j} =\binom{m-2}{2j-2}+2\binom{m-2}{2j-1}+\binom{m-2}{2j}=\)

\(\displaystyle =\binom{m-3}{2j-3}+3\binom{m-3}{2j-2}+3\binom{m-3}{2j-1}+\binom{m-3}{2j},\)

ahol az \(\displaystyle \binom{a}{b}\) kifejezés értékét \(\displaystyle b<0\) és \(\displaystyle a<b\) esetén is 0-nak tekintjük. Ezt felhasználva

\(\displaystyle S_m=\sum_{j=0}^{[m/2]} \left(\binom{m-3}{2j-3}+3\binom{m-3}{2j-2}+3\binom{m-3}{2j-1} +\binom{m-3}{2j}\right){(-3)}^j. \)

Számoljuk meg, hogy ebben az összegben mi lesz \(\displaystyle \binom{m-3}{\ell}\) együtthatója, ha \(\displaystyle 0\le \ell\le m-3\). Ha \(\displaystyle \ell=2k+1\) páratlan szám, akkor a kérdéses együttható

\(\displaystyle 1\cdot {(-3)}^{k+2}+3\cdot {(-3)}^{k+1}=0, \)

ha pedig \(\displaystyle \ell=2k\) páros, akkor

\(\displaystyle 3\cdot{(-3)}^{k+1}+1\cdot{(-3)}^{k}=-8\cdot {(-3)}^k. \)

Azaz

\(\displaystyle S_m=\sum_{k=0}^{[(m-3)/2]} \binom{m-3}{2k}(-8){(-3)}^k=-8 S_{m-3}. \)

Ezzel igazoltuk, hogy a kérdezett összeg értéke 3-mal osztható \(\displaystyle n\) esetén \(\displaystyle 2^{2n}\), 3-mal nem osztható \(\displaystyle n\) esetén pedig \(\displaystyle -2^{2n-1}\).

Baran Zsuzsanna (Debrecen, Fazekas M. Gimn.), 9. évf.

Statisztika:

33 dolgozat érkezett.
5 pontot kapott:	Ágoston Péter, Baran Zsuzsanna, Bereczki Zoltán, Csépai András, Csernák Tamás, Di Giovanni Márk, Fekete Panna, Fonyó Viktória, Geng Máté, Győrfi-Bátori András, Katona Dániel, Kovács 972 Márton, Kúsz Ágnes, Lajkó Kálmán, Maga Balázs, Mócsy Miklós, Nagy-György Pál, Öreg Botond, Schwarcz Tamás, Seress Dániel, Williams Kada.
4 pontot kapott:	Forrás Bence, Gyulai-Nagy Szuzina, Leitereg Miklós, Schefler Barna.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2014. májusi matematika feladatai