Feladat: F.2526 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Bán Rita ,  Beke T. ,  Bóna M. ,  Boros Z. ,  Csizmadia Gy. ,  Deák Csaba ,  Dinnyés Enikő ,  Edvi T. ,  Fülöp T. ,  Grallert Ágnes ,  Heller Judit ,  Hetyei Judit ,  Íjjas Cs. ,  Kocsis 443 Katalin ,  Kós G. ,  Licsik I. ,  Ligeti Z. ,  Limbek Cs. ,  Majzik I. ,  Makay G. ,  Montágh B. ,  Olasz-Szabó M. ,  Pfeil T. ,  Pintér A. ,  Regős G. ,  Ribényi Á. ,  Sobor G. 
Füzet: 1986/november, 361 - 362. oldal  PDF file
Témakör(ök): Összefüggések binomiális együtthatókra, Kombinatorikai leszámolási problémák, Kombinációk, Variációk, Számsorozatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1985/április: F.2526

Bizonyítsuk be, hogy ha 0kn-1 egész számok, akkor
j=0k(nj)=j=0k(n-1-jk-j)2j(1)

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.

I. megoldás. Próbáljunk jelentést tulajdonítani az egyenlőség két oldalán álló mennyiségeknek! Tekintsük ehhez az n hosszúságú 0‐1 sorozatokat. Azoknak a sorozatoknak a száma, amelyek pontosan j darab 1-est tartalmaznak, éppen (nj), az 1-esek helyét ugyanis ennyiféleképpen választhatjuk meg. Az egyenlőség bal oldalán eszerint azoknak az n hosszúságú 0‐1 sorozatoknak a száma áll, amelyek pontosan 0,1,2,...,k darab azaz legfeljebb k darab 1-est tartalmaznak.
Vegyük most szemügyre a jobb oldalon álló összeg egy tagját. Az első tényező, (n-1-jk-j) azoknak az n-1-j hosszúságú 0‐1 sorozatoknak a száma, amelyek k-j darab 1-est tartalmaznak. Ami a második tényezőt illeti, összesen 2j darab j hosszúságú 0‐1 sorozat van. A szorzat így azoknak az n-1 hosszúságú 0‐1 sorozatoknak a száma, amelyekben az első n-1-j helyen éppen k-j darab 1-es fordul elő. Ha minden egyes ilyen sorozatban az (n-j)-edik helyre egy 0-t illesztünk, akkor olyan, most már n hosszúságú sorozatokat kapunk, amelyekben legfeljebb k darab 1-es van, az első n-1-j elem között pontosan k-j, az utolsó j elem között pedig legfeljebb j. Az utólag beillesztett 0 pedig éppen az (n-k)-adik 0 a sorozatban.
Csoportosítsuk tehát aszerint a legfeljebb k darab 1-est ‐ és így legalább n-k darab 0-t ‐ tartalmazó n hosszúságú 0‐1 sorozatokat, hogy az n-k-adik 0 hányadik helyen fordul elő a sorozatban. Ennek a 0-nak a pozíciója (n-k)-tól n-ig változhat, tekintsük azt az esetet, amikor ez épp az (n-j)-edik elem (0jk). Ekkor az ezt a 0-t megelőző n-j-1 elem között n-k-1 darab 0 és így k-j darab 1-es van, az utolsó j elem mindegyike lehet 0 vagy 1, az ilyen sorozatok száma tehát valóban (n-1-jk-j)2j. Így az összes olyan 0‐1 sorozatok száma, amelyek legfeljebb k darab 1-est tartalmaznak, valóban

j=0k(n-1-jk-j)2j

II. megoldás. Az n-re vonatkozó teljes indukcióval bizonyítjuk az állítást. Ha k=0, akkor a bizonyítandó egyenlőség minden n-re az 1=1 alakot ölti, ha pedig k=n-1, akkor ugyancsak minden n-re a bal oldal
j=0n-1(nj)=2n-1,
a jobb oldal pedig
j=0n-1(n-1-jn-1-j)2j=j=0n-12j=2n-1,
az állítás tehát minden n-re igaz, ha k=0 vagy k=n-1. Innen következik, hogy n=1 és n=2 esetekben fennáll (1).
Tegyük most fel, hogy 1kn-1 és az állítás n-1-re igaz. Ekkor az (n-1,k) és az (n-1,k-1) párokra értelmes és igaz az (1) egyenlőség, azaz
j=0k(n-1j)=j=0k(n-2-jk-j)2j,és(2)j=0k-1(n-1j)=j=0k-1(n-2-jk-j-1)2j.(3)



A (3) összefüggés bal oldala j=1k(n-1j-1) alakban is írható. Ha összeadjuk a két egyenlőséget, és felhasználjuk az (m0)=1, illetve az (mr)+(mr-1)=(m+1r) összefüggéseket, akkor éppen a bizonyítandó állítást kapjuk.
 
Megjegyzés. A legtöbb megoldás k-ra vonatkozó teljes indukciót használt. Volt, aki észrevette, hogy az f(n,k)+f(n,k+1)=f(n+1,k+1) összefüggés fennáll az (1) két oldalán szereplő mennyiségekre és így a kezdeti értékek egyenlőségéből következik az állítás.