A B. 5141. feladat (2020. december)

B. 5141. Bizonyítsuk be, hogy

$\displaystyle \sum_{i=0}^n\, \sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1} = 2^{2n}.$

Javasolta: Nagy Dávid (Cambridge)

(6 pont)

A beküldési határidő 2021. január 11-én LEJÁRT.

1. megoldás: algebrázós. A $\displaystyle \sum_{i=0}^n \sum_{j=i}^n \binom{n}{i}\binom{n+1}{j+1}$ összegben a belső szumma tekintetében $\displaystyle \binom{n}{i}$ egy konstans szorzónak számít, tehát kiemelhető belőle:

$\displaystyle \sum_{i=0}^n \sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1} = \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i}^n \binom{n+1}{j+1} \right).$

Közismert, hogy $\displaystyle \binom{k}{\ell} = \binom{k}{k-\ell}$ (tetszőleges $\displaystyle k,\ell$ egészek esetén), így:

$\displaystyle \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i}^n \binom{n+1}{j+1} \right) = \sum_{i=0}^n \left( \binom{n}{n-i} \sum_{j=i}^n \binom{n+1}{n-j} \right).$

Nézzük meg a belső szummát közelebbről:

$\displaystyle S(i) = \sum_{j=i}^n \binom{n+1}{n-j} = \binom{n+1}{n-i} + \binom{n+1}{n-i-1} + \ldots + \binom{n+1}{1} + \binom{n+1}{0} = \sum_{j=0}^{n-i} \binom{n+1}{j} = S'(i).$

Ekkor persze:

$\displaystyle \sum_{i=0}^n \left( \binom{n}{n-i} \sum_{j=i}^n \binom{n+1}{n-j} \right) = \sum_{i=0}^n \binom{n}{n-i} S(i) = \sum_{i=0}^n \binom{n}{i} S(n-i) = \sum_{i=0}^n \binom{n}{i} S'(n-i) = \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=0}^{i} \binom{n+1}{j} \right).$

Következésképpen:

Ez éppen a bizonyítandó egyenlet kétszerese.

2. megoldás: valszámos. Nevezzük Segédfeladatnak a következő kérdést:
Anna $\displaystyle n$-szer, Balázs $\displaystyle n+1$-szer dob fel egy (szabályos) pénzérmét. Mennyi az esélye, hogy Balázs többször dobott fejet, mint Anna? (ez egy ismert feladat, ld. pl. https://matkonyv.fazekas.hu/cache/pdf/vol_valszam_ii.pdf 11.15 feladat)
Annak az esélye, hogy Anna éppen $\displaystyle i$ fejet dob.

$\displaystyle \frac{\binom{n}{i}}{2^n}.$

Annak az esélye, hogy Balázs $\displaystyle i$-nél több fejet dob:

$\displaystyle \frac{\sum_{j=i+1}^{n+1} \binom{n+1}{j}}{2^{n+1}} = \frac{\sum_{j=i}^n \binom{n+1}{j+1}}{2^{n+1}}.$

Tehát annak az esélye, hogy Anna pontosan $\displaystyle i$ fejet dob, míg Balázs ennél több fejet dob:

$\displaystyle \frac{\binom{n}{i}}{2^n} \cdot \frac{\sum_{j=i}^n \binom{n+1}{j+1}}{2^n} = \frac{\sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1}}{2^{2n+1}}.$

Így annak az esélye, hogy Annánál Balázs több fejet dob:

$\displaystyle \frac{\sum_{i=0}^n \sum_{j=i}^n \binom{n}{i}\binom{n+1}{j+1}}{2^{2n+1}}.$

Ez tehát a segédfeladat kérdésére a válasz; egyben a bizonyítandó egyenlet bal oldalának $\displaystyle \frac1{2^{2n+1}}$ része.

Elegendő tehát belátnunk, hogy a segédfeladatunkra a válasz $\displaystyle \frac12$. Erre mutatunk egy szép indoklást. Tegyük fel, hogy Anna és Balázs egyidőben dobálják fel a pénzérméiket, és számolják a fejeket. Állítsuk meg a játékot egy pillanatra akkor, amikor mindketten az $\displaystyle n$-edik dobásuk után járnak (Anna ekkor már befejezte, Balázsnak még van egy utolsó dobása).

1. Ha Balázsnak már eddig is több fej dobása van, akkor biztosan több lesz neki a végén is (hiszen Anna már nem dob).
2. Ha ebben a pillanatban Annának több feje van, akkor biztosan nem lehet Balázsnak több a végén (hisz már csak egy dobása van).
3. Ha a vizsgált pillanatban döntetlen az állás, akkor Balázs utolsó dobásától függően, $\displaystyle 1/2$ eséllyel fog teljesülni, hogy ő fejet dob.

Ha az egyes esetek valószínűségét $\displaystyle P_1,P_2,P_3$-mal jelöljük, akkor tehát annak az esélye, hogy Balázs több fejet dob, éppen $\displaystyle P_1 + \frac12P_3$. Mivel a szimmetria okán $\displaystyle P_1 = P_2$, illetve nyilván $\displaystyle 1 = P_1+P_2+P_3$, így a keresett valószínűség tényleg $\displaystyle \frac12$.

Statisztika:

71 dolgozat érkezett.
6 pontot kapott:	64 versenyző.
5 pontot kapott:	2 versenyző.
4 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2020. decemberi matematika feladatai