Kezdőlap


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 \| MathML
Témakör(ök):	Rekurzív sorozatok, Feladat
Hivatkozás(ok):	Feladatok: 2004/november: B.3771

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 $a_{n, k} = \frac{1}{k \cdot (\binom{n}{k})}$ és $b_{n, k} = \frac{1}{k \cdot 2^{n - k}}$ , $k = 1,2, ..., n$ . Ha $A_{n} = \sum_{k = 1}^{n} a_{n, k}$ és $B_{n} = \sum_{k = 1}^{n} b_{n, k}$ , akkor az $A_{n} = B_{n}$ egyenlőséget kell igazolnunk.
$A_{1} = B_{1} = 1$ nyilvánvalóan igaz. Megmutatjuk, hogy az $A_{n}$ és a $B_{n}$ sorozatokra egyaránt teljesül az

\begin{matrix} x_{n + 1} = \frac{x_{n}}{2} + \frac{1}{n + 1} \end{matrix}

(*)

rekurzió, ebből pedig következik a bizonyítandó egyenlőség.
A

B_{n}

sorozat esetében ez majdnem nyilvánvaló. Ha ugyanis

1 \leq k \leq n

, akkor

b_{n + 1, k} = \frac{1}{k} \cdot \frac{1}{2^{n + 1 - k}} = \frac{1}{2} b_{n, k}

, tehát

B_{n + 1} - b_{n + 1, n + 1} = \frac{1}{2} B_{n}

. Rendezés után innen valóban a

(*)

rekurziót kapjuk, hiszen

b_{n + 1, n + 1} = \frac{1}{n + 1}

.
Az

A_{n}

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

a_{n, k}

sorozat elemeit írjuk (ábra), akkor az így kapott elrendezésben minden elem az alsó két szomszédjának az összege:

\begin{matrix} a_{n, k} = a_{n + 1, k} + a_{n + 1, k + 1} . \end{matrix}

(1)

Az (1) egyenlőség egyszerű számolással adódik. Az

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

azonosságot felhasználva azt kell megmutatnunk, hogy

\begin{matrix} \frac{k! (n - k)!}{k \cdot n!} = \frac{k! (n + 1 - k)!}{k \cdot (n + 1)!} + \frac{(k + 1)! (n - k)!}{(k + 1) \cdot (n + 1)!} . \end{matrix}

Ha szorzunk

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

-sal, akkor egyszerűsítés és összevonás után a nyilvánvalóan igaz

\begin{matrix} \frac{1}{k} = \frac{n + 1 - k}{k \cdot (n + 1)} + \frac{k + 1}{(k + 1) (n + 1)} = \frac{(n + 1 - k) + k}{k \cdot (n + 1)} = \frac{n + 1}{k \cdot (n + 1)} \end{matrix}

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ő,

a_{n + 1,1}

és

a_{n + 1, n + 1}

egyszer, a többiek pedig kétszer. Ez azt jelenti, hogy az

n

-edik sor elemeinek az összege,

A_{n} = 2 A_{n + 1} - a_{n + 1,1} - a_{n + 1, n + 1}

. Mivel pedig

a_{n + 1,1} = a_{n + 1, n + 1} = \frac{1}{n + 1}

, innen valóban

A_{n + 1} = \frac{A_{n}}{2} + \frac{1}{n + 1}

adódik, és ezt akartuk bizonyítani.

Megjegyzés. Az

a_{n, 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

a_{n, p} = a_{n, q}