Problem B. 4640. (May 2014)
B. 4640. Calculate the value of the sum \(\displaystyle \sum_{j=0}^{n} \binom{2n}{2j} {(-3)}^{j}\).
(5 pont)
Deadline expired on June 10, 2014.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
33 students sent a solution. 5 points: Á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 points: Forrás Bence, Gyulai-Nagy Szuzina, Leitereg Miklós, Schefler Barna. 3 points: 2 students. 2 points: 2 students. 1 point: 1 student. 0 point: 3 students.
Problems in Mathematics of KöMaL, May 2014