Feladat: F.1822 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Meszéna Géza 
Füzet: 1972/december, 210 - 211. oldal  PDF file
Témakör(ök): Összefüggések binomiális együtthatókra, Kombinációk, Feladat
Hivatkozás(ok):Feladatok: 1972/április: F.1822

Bizonyítsuk be, hogy fennáll a következő egyenlőség:
i=0n-k(ni)(ni+k)=(2nn+k),(1)
ahol n és k (kn) természetes számok.

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A bizonyítandó egyenlőség jobb oldalán 2n (különböző) elem (n+k)-adosztályú (ismétlés nélküli) kombinációjának a száma áll. Megmutatjuk, hogy a bal oldali összeg ugyanezt adja, a kombinációknak egy bizonyos szempont szerint osztályokba rendezése után ‐ amikor minden kombinációt egy és csak egy osztályba sorolunk be ‐, mert az összeg tagjai éppen az egyes osztályokba sorolt kombinációk számai.
Gondoljuk, hogy elemeink egy iskola két párhuzamos osztályának, A-nak és B-nek tanulói, mindkét osztályban n tanuló van, és köztük (n+k) jegyet kívánunk kiosztani valamilyen rendezvényre. A kiosztási lehetőségek száma ‐ az A-ba vagy B-be tartozást nem tekintve ‐ éppen (1) jobb oldala.
Azokban a kombinációkban (kiosztásokban), amelyekben az A osztály minden tanulója kap jegyet, a B-sek közül csak (n+k)-n=k kap. Az ilyenek száma ‐ mindjárt átalakítva célunk szerint :

(nk)=1(nk)=(n0)(nk),(2)

Ha az A-ból 1 tanulót ‐ majd általában i számú tanulót ‐ törlünk, akkor B-ből, 1-gyel ‐ illetve i-vel ‐ többen kapnak jegyet, és a kiosztási lehetőségek száma :
(n1)(nk+1),(ni)(nk+i),(i=1,2,...)(3)
mert az első tényező az A-beli törlési, a második a B-beli kiválasztási lehetőségek száma. A (3) kifejezésben felismerjük (1) bal oldalának általános tagját.
i-t csak addig van értelme növelnünk, míg a B-ben már mind az n tanuló kap jegyet, vagyis míg az A-ban már csak k tanuló kap, azaz míg itt n-k tanulót töröltünk. Éppen ez az (1) bal oldalán i legnagyobb figyelembe veendő értéke, tehát (2) és (3) alatt felsoroltuk egyrészt (1) bal oldalának összes tagját, másrészt az (n+k) jegy kiosztásának minden lehetőségét egyszer és csak egyszer. E két szám egyenlőségét akartuk bizonyítani.
 

Meszéna Géza (Budapest, Berzsenyi D. Gimn., II. o. t.)
 

Megjegyzések. 1. Írhatnánk a bal oldali összegezésben n-k helyett bármely nagyobb egész számot is, mert az így hozzágondolt tagok ‐ szorzatok ‐ egyik tényezője úgyis 0 lenne.
2. Általában az is igaz, hogy
(MN)=i=0m(mi)(M-nN-i).
ahol m, M, N természetes számok, és M nagyobb N-nél és m-nél.