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