Kezdőlap


Feladat:	B.4529	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Csernák Tamás , Kabos Eszter , Mócsy Miklós , Venczel Tünde
Füzet:	2014/április, 203 - 208. oldal		PDF \| MathML
Témakör(ök):	Feladat, Számsorozatok, Binomiális együtthatók
Hivatkozás(ok):	Feladatok: 2013/március: B.4529

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. Mivel az állításban szereplő egyenlőség jobb oldala zárt, próbáljuk a bal oldalt szintén zárt alakra hozni. Ehhez emeljünk ki az összegből 2-t, majd használjuk fel a szumma felbonthatóságát, és ismét emeljünk ki, ezúttal

n

-et. Ezután, mivel

i = n

-re

n - i = 0

‐ vagyis a második szumma utolsó tagja 0 ‐ azt a tagot hagyjuk el:

\begin{matrix} \sum_{i = 1}^{n} 2 i (\binom{2 n}{n - i}) & = 2 (\sum_{i = 1}^{n} (n - (n - i)) (\binom{2 n}{n - i})) = \\ = 2 (n \sum_{i = 1}^{n} (\binom{2 n}{n - i}) - \sum_{i = 1}^{n - 1} (n - i) (\binom{2 n}{n - i})) : = A . \end{matrix}

Az első szumma a Pascal-háromszög

2 n

-edik sorában adja össze a tagokat a 0-t tartalmazótól az (

n - 1

)-et tartalmazóig.

Ennek a sornak

2 n + 1

eleme van és szimmetrikus a középső elemére

(

hiszen

(\binom{m}{k}) = (\binom{m}{m - k}))

, ami

(\binom{2 n}{n})

. Tudjuk még, hogy a Pascal-háromszög

m

-edik sorának a tagösszege

2^{m}

, ezért a fenti összeg így írható:

\begin{matrix} \sum_{i = 1}^{n} (\binom{2 n}{n - i}) = \frac{\sum_{i = 1}^{2 n} (\binom{2 n}{i}) - (\binom{2 n}{n})}{2} = \frac{2^{2 n} - (\binom{2 n}{n})}{2} . \end{matrix}

Tehát

\begin{matrix} A & = 2 (n \cdot \frac{2^{2 n} - (\binom{2 n}{n})}{2} - \sum_{i = 1}^{n - 1} (n - i) (\binom{2 n}{n - i})) = \\ = 2 (n \cdot 2^{2 n - 1} - \frac{n}{2} (\binom{2 n}{n}) - \sum_{i = 1}^{n - 1} (n - i) (\binom{2 n}{n - i})) : = B . \end{matrix}

Fordítsuk most figyelmünket a megmaradt szummában lévő kifejezésre. Ha olyan alakra tudnánk hozni, amiben szintén csak egy sor elemeit kell összegeznünk, akkor zárt alakú lenne. Alakítsuk hát át a következő, a Pascal-háromszög tagjainak explicit felírásából következő egyenlőség segítségével:

\begin{matrix} (n - i) (\binom{2 n}{n - i}) & = (n - i) \cdot \frac{(2 n)!}{(n - i)! (n + i)!} = 2 n \cdot \frac{(2 n - 1)!}{(n - i - 1)! (n + i)!} = \\ = 2 n (\binom{2 n - 1}{n - i - 1}) . \end{matrix}

Tehát

\begin{matrix} B = 2 (n \cdot 2^{2 n - 1} - \frac{n}{2} (\binom{2 n}{n}) - 2 n \sum_{i = 1}^{n - 1} (\binom{2 n - 1}{n - i - 1})) . \end{matrix}

A szummában szereplő összeg a Pascal-háromszög (

2 n - 1

)-edik sorának a tagösszege a nullát tartalmazótól az (

n - 2

)-t tartalmazóig. Ebben a

2 n

elemű sorban az első

n

elem összege ugyanannyi, mint a második

n

elemé. Így a következő átalakításokat végezhetjük:

\begin{matrix} \sum_{i = 1}^{n - 1} (\binom{2 n - 1}{n - i - 1}) = \frac{\sum_{i = 1}^{2 n - 1} (\binom{2 n - 1}{i})}{2} - (\binom{2 n - 1}{n - 1}) = \frac{2^{2 n - 1}}{2} - (\binom{2 n - 1}{n - 1}) . \end{matrix}

A bal oldal tehát, a végén felhasználva a tagok szimmetriáját, majd a Pascal-háromszög rekurzív definícióját:

\begin{matrix} 2 (n \cdot 2^{2 n - 1} - \frac{n}{2} (\binom{2 n}{n}) - 2 n (\frac{2^{2 n - 1}}{2} - (\binom{2 n - 1}{n - 1}))) = \\ = & 2 (n \cdot 2^{2 n - 1} - \frac{n}{2} (\binom{2 n}{n}) - n \cdot 2^{2 n - 1} + 2 n (\binom{2 n - 1}{n - 1})) = \\ = & n \cdot (4 (\binom{2 n - 1}{n - 1}) - (\binom{2 n}{n})) = \\ = & n \cdot (2 (\binom{2 n - 1}{n - 1}) + 2 (\binom{2 n - 1}{n}) - (\binom{2 n}{n})) = n (2 (\binom{2 n}{n}) - (\binom{2 n}{n})) = n (\binom{2 n}{n}) . \end{matrix}

Ezzel igazoltuk az állítást.

II. megoldás. Az állítást teljes indukcióval bizonyítjuk. Ha

n = 1

, akkor

2 \cdot (\binom{2}{0}) = 2

és

1 \cdot (\binom{2}{2}) = 1

, tehát igaz az állítás.
Tegyük fel, hogy az állítás

n

-re igaz, és bizonyítsuk be

n + 1

-re. Felhasználjuk, hogy

(\binom{n}{k}) + (\binom{n}{k + 1}) = (\binom{n + 1}{k + 1})

\begin{matrix} \sum_{i = 0}^{n + 1} 2 i (\binom{2 n + 2}{n + 1 - i}) = \sum_{i = 0}^{n + 1} 2 i ((\binom{2 n + 1}{n + 1 - i}) + (\binom{2 n + 1}{n - i})) = \\ = & \sum_{i = 0}^{n + 1} 2 i ((\binom{2 n}{n + 1 - i}) + (\binom{2 n}{n - i}) + (\binom{2 n}{n - i}) + (\binom{2 n}{n - i - 1})) = \\ = & \sum_{i = 0}^{n + 1} (2 i (\binom{2 n}{n + 1 - i}) + 4 i (\binom{2 n}{n - i}) + 2 i (\binom{2 n}{n - i - 1})) . \end{matrix}

Az első szummába

j = i - 1

-et, a másodikba

j = i

-t, a harmadikba

j = i + 1

-et helyettesítve és a 0-s szorzókat tartalmazó tagokat elhagyva az összeg így is írható:

\begin{matrix} \sum_{j = 0}^{n} (2 j + 2) (\binom{2 n}{n - j}) + \sum_{j = 1}^{n + 1} 4 j (\binom{2 n}{n - j}) + \sum_{j = 2}^{n + 2} (2 j - 2) (\binom{2 n}{n - j}) = \\ = & \sum_{j = 2}^{n} [(2 j + 2) + 4 j + (2 j - 2)] (\binom{2 n}{n - j}) + 2 (\binom{2 n}{n}) + 4 (\binom{2 n}{n - 1}) + 4 (\binom{2 n}{n - 1}) = \\ = & \sum_{j = 2}^{n} 8 j (\binom{2 n}{n - j}) + 8 (\binom{2 n}{n - 1}) + 2 (\binom{2 n}{n}) = 4 \sum_{j = 1}^{n} (2 j (\binom{2 n}{n - j})) + 2 (\binom{2 n}{n}) . \end{matrix}

Az indukciós feltevést felhasználva ezt a következő alakra hozhatjuk:

\begin{matrix} = 4 n (\binom{2 n}{n}) + 2 (\binom{2 n}{n}) = (4 n + 2) (\binom{2 n}{n}) = (n + 1) \frac{(2 n + 1) (2 n + 2)}{(n + 1) (n + 1)} (\binom{2 n}{n}) = \\ = (n + 1) \frac{(2 n + 2)!}{(n + 1)! (n + 1)!} = (n + 1) (\binom{2 n + 2}{n + 1}) . \end{matrix}

III. megoldás. Megmutatjuk, hogy ha

n

és

k

pozitív egészek, akkor

\begin{matrix} \sum_{i = n - k + 1}^{n} 2 i \cdot (\binom{2 n}{n - i}) = k \cdot (\binom{2 n}{k}) . \end{matrix}

Ezt az általánosabb összefüggést látjuk be

k

-ra vonatkozó teljes indukcióval.

k = 1

esetén az állítás:

\begin{matrix} 2 n \cdot (\binom{2 n}{0}) = 1 \cdot (\binom{2 n}{1}) . \end{matrix}

Mivel mindkét oldal

2 n

-nel egyenlő, az állítás igaz.
Tegyük fel, hogy az állítás teljesül

k = m

esetén:

\begin{matrix} \sum_{i = n - m + 1}^{n} 2 i \cdot (\binom{2 n}{n - i}) = m \cdot (\binom{2 n}{m}) . \end{matrix}

Bizonyítsuk be

k = m + 1

-re. Ekkor az állítás:

\begin{matrix} \sum_{i = n - m}^{n} 2 i \cdot (\binom{2 n}{n - i}) = (m + 1) \cdot (\binom{2 n}{m + 1}) . \end{matrix}

A bal oldali összeg első tagját kiszedve a szummából:

\begin{matrix} 2 (n - m) \cdot (\binom{2 n}{m}) + \sum_{i = n - m + 1}^{n} 2 i \cdot (\binom{2 n}{n - i}) = (m + 1) \cdot (\binom{2 n}{m + 1}) . \end{matrix}

Az indukciós feltételt felhasználva:

\begin{matrix} 2 (n - m) \cdot (\binom{2 n}{m}) & = (m + 1) \cdot (\binom{2 n}{m + 1}) - m \cdot (\binom{2 n}{m}), \\ (2 n - m) \cdot (\binom{2 n}{m}) & = (m + 1) \cdot (\binom{2 n}{m + 1}) . \end{matrix}

Bontsuk ki a binominális együtthatókat:

\begin{matrix} (2 n - m) \cdot \frac{(2 n)!}{m! (2 n - m)!} = \frac{(2 n)!}{m! (2 n - m - 1)!}, \end{matrix}

illetve

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

Ezzel a tételt teljes indukcióval bizonyítottuk. Ennek egy speciális esete volt a feladatban kitűzve, ahol

k = n

, amire az állítás az általános tételből triviálisan következik.

IV. megoldás. A megoldás során bizonyítandó egyenlőség bal oldalát jelölje

\begin{matrix} B = \sum_{i = 1}^{n} 2 i \cdot (\binom{2 n}{n - i}), \end{matrix}

a jobb oldalát pedig

\begin{matrix} J = n \cdot (\binom{2 n}{n}) . \end{matrix}

Tekintsünk egy véletlen bolyongást az egész számokon: Egy bolha az origóból indul és

\frac{1}{2}

valószínűséggel jobbra, ugyanilyen valószínűséggel balra ugrik 1-et, majd az előző lépéstől függetlenül,

\frac{1}{2}

valószínűséggel jobbra, ugyanilyen valószínűséggel balra ugrik 1-et, és így tovább.
Értelmezzük az

X_{2 n}

valószínűségi változót a következőképpen:

X_{2 n} : =

a bolyongás

2 n

-edik lépésében a bolha helye. Ekkor

X_{2 n}

lehetséges értékei a

[- 2 n,2 n]

intervallum páros értékű helyei. Ha a jobbra lépések száma

j

, akkor a balra lépéseké

2 n - j

. Ha a bolha a

2 i

-re lépett

2 n

lépés után, akkor

j - (2 n - j) = 2 i

, amiből

j = n + i

. Innen

\begin{matrix} P (X_{2 n} = 2 i) = \frac{1}{2^{2 n}} \cdot (\binom{2 n}{n + i}) = \frac{1}{2^{2 n}} \cdot (\binom{2 n}{n - i}), \end{matrix}

ahol

i \in [- n, n]

, egész.
Legyen

\begin{matrix} S_{2 n} = E (| X_{2 n} |) = \frac{1}{2^{2 n}} \cdot \sum_{i = - n}^{n} 2 \cdot | i | \cdot (\binom{2 n}{n - i}) . \end{matrix}

S_{2 n} = 2 \cdot \frac{1}{2^{2 n}} \cdot B

, hiszen

i = 0

esetén az összegben 0 szerepel.

Ha belátjuk, hogy

S_{2 n} = 2 \cdot \frac{1}{2^{2 n}} \cdot J

, akkor abból valóban

J = B

következik.

Lemma:

\begin{matrix} S_{2 n + 1} = S_{2 n} + \frac{1}{2^{2 n}} \cdot (\binom{2 n}{n}) és S_{2 n + 2} = S_{2 n + 1} . \end{matrix}

A lemma bizonyítása: A második egyenlőség triviális, mert a (

2 n + 1

)-edik lépés után a bolha egy páratlan, tehát 0-tól különböző helyen van, tehát

| X_{2 n + 2} | - | X_{2 n + 1} |

értéke mindentől függetlenül

\frac{1}{2}

valószínűséggel

- 1

, és ugyanilyen valószínűséggel

+ 1

. Az első egyenlőséghez egyrészt azt kell megjegyezni, hogy a várható érték számításánál az

X_{2 n} = 0

-hoz tartozó összeadandó az

i

-vel való szorzás miatt 0, viszont ha a bolha a

2 n

-edik lépésben a origóban volt, akkor a (

2 n + 1

)-edik lépésben pontosan 1 lesz

| X_{2 n + 1} |

értéke. Ez az esemény

\begin{matrix} P (X_{2 n} = 0) = \frac{1}{2^{2 n}} \cdot (\binom{2 n}{n}) \end{matrix}

valószínűséggel következik be.

Állítás:

\begin{matrix} S_{2 n} = 2 \cdot \frac{1}{2^{2 n}} \cdot n \cdot (\binom{2 n}{n}) . \end{matrix}

Bizonyítás: Teljes indukcióval:

n = 1

re igaz. Feltéve az

n

-re vonatkozó állítást,

n + 1

-re fogjuk igazolni.
A lemma miatt:

\begin{matrix} S_{2 n + 2} & = S_{2 n + 1} = S_{2 n} + \frac{1}{2^{2 n}} \cdot (\binom{2 n}{n}) = 2 \cdot \frac{1}{2^{2 n}} \cdot n \cdot (\binom{2 n}{n}) + \frac{1}{2^{2 n}} \cdot (\binom{2 n}{n}) = \\ = \frac{1}{2^{2 n}} \cdot (2 n + 1) \cdot (\binom{2 n}{n}) = \frac{1}{2^{2 n}} \cdot (2 n + 1) \cdot \frac{(2 n)!}{n! n!} = \\ = \frac{1}{2^{2 n}} \cdot \frac{(2 n + 2) (2 n + 1) (2 n)!}{2 (n + 1) n! n!} \cdot \frac{n + 1}{n + 1} = \\ = \frac{1}{2^{2 n}} \cdot \frac{1}{2} \cdot \frac{(2 n + 2)!}{(n + 1)! (n + 1)!} \cdot (n + 1) = \frac{1}{2^{2 n}} \cdot \frac{n + 1}{2} (\binom{2 n + 2}{n + 1}) = \\ = 2 \cdot \frac{1}{2^{2 n + 2}} \cdot (n + 1) (\binom{2 n + 2}{n + 1}), \end{matrix}

ami éppen az

n + 1

-re vonatkozó állítás.
Ezzel a teljes indukciót befejeztük. A feladat állítását beláttuk.