Feladat: B.3771 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Bogár Péter ,  Bozsár Erik ,  Dobos Gábor ,  Eckert Bernadett ,  Estélyi István ,  Gyenizse Gergő ,  Halász Veronika ,  Horváth Zoltán ,  Hujter Bálint ,  Kisfaludi-Bak Sándor ,  Kiss-Tóth Christian ,  Kónya Gábor ,  Kovács Péter ,  Kutas Péter ,  Lorántfy Bettina ,  Magda Gábor ,  Mészáros Gábor ,  Nagy Csaba ,  Nagy János ,  Nagy Péter ,  Poronyi Balázs ,  Radnai András ,  Strenner Balázs ,  Szilágyi Csaba ,  Tomon István ,  Tossenberger Anna ,  Udvari Balázs ,  Ureczky Bálint 
Füzet: 2005/szeptember, 349 - 350. oldal  PDF file
Témakör(ök): Rekurzív sorozatok, Feladat
Hivatkozás(ok):Feladatok: 2004/november: B.3771

Legyen ak=1(nk), bk=12n-k, k=1,2,...,n.
Bizonyítsuk be, hogy
a1+a22+a33+...+ann=b1+b22+b33+...+bnn.

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.

Megoldás. A feladat jelöléseit némileg módosítva legyen an,k=1k(nk) és bn,k=1k2n-k, k=1,2,...,n. Ha An=k=1nan,k és Bn=k=1nbn,k, akkor az An=Bn egyenlőséget kell igazolnunk.
A1=B1=1 nyilvánvalóan igaz. Megmutatjuk, hogy az An és a Bn sorozatokra egyaránt teljesül az

xn+1=xn2+1n+1(*)
rekurzió, ebből pedig következik a bizonyítandó egyenlőség.
A Bn sorozat esetében ez majdnem nyilvánvaló. Ha ugyanis 1kn, akkor bn+1,k=1k12n+1-k=12bn,k, tehát Bn+1-bn+1,n+1=12Bn. Rendezés után innen valóban a (*) rekurziót kapjuk, hiszen bn+1,n+1=1n+1.
Az An sorozat vizsgálatához először megmutatjuk, hogy az összeg tagjaira egy ,,fordított'' Pascal-háromszög-szerű összefüggés teljesül: ha egy háromszög alakú táblázat n-edik sorába az an,k sorozat elemeit írjuk (ábra), akkor az így kapott elrendezésben minden elem az alsó két szomszédjának az összege:
an,k=an+1,k+an+1,k+1.(1)
Az (1) egyenlőség egyszerű számolással adódik. Az (nk)=n!k!(n-k)! azonosságot felhasználva azt kell megmutatnunk, hogy
k!(n-k)!kn!=k!(n+1-k)!k(n+1)!+(k+1)!(n-k)!(k+1)(n+1)!.
Ha szorzunk (nk)=n!k!(n-k)!-sal, akkor egyszerűsítés és összevonás után a nyilvánvalóan igaz
1k=n+1-kk(n+1)+k+1(k+1)(n+1)=(n+1-k)+kk(n+1)=n+1k(n+1)
egyenlőséget kapjuk.
 
 

Az (1) rekurzió szerint a táblázat n-edik sorában álló elemek összegében az (n+1)-edik sor elemei vesznek részt: a két szélső, an+1,1 és an+1,n+1 egyszer, a többiek pedig kétszer. Ez azt jelenti, hogy az n-edik sor elemeinek az összege, An=2An+1-an+1,1-an+1,n+1. Mivel pedig an+1,1=an+1,n+1=1n+1, innen valóban An+1=An2+1n+1 adódik, és ezt akartuk bizonyítani.
 
Megjegyzés. Az an,k számok a binomiális együtthatókéra emlékeztető szimmetriával is rendelkeznek: könnyű igazolni, hogy ha p+q=n+1, akkor an,p=an,q.