Problem B. 5141. (December 2020)
B. 5141. Prove that
\(\displaystyle \sum_{i=0}^n\, \sum_{j=i}^n \binom{n}{i} \binom{n+1}{j+1} = 2^{2n}. \)
Proposed by Dávid Nagy, Cambridge
(6 pont)
Deadline expired on January 11, 2021.
Sorry, the solution is available only in Hungarian. Google translation
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:
$$\begin{eqnarray*} 2 \cdot \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) + \sum_{i=0}^n \left( \binom{n}{n-i} \sum_{j=i}^n \binom{n+1}{n-j} \right) = \\ &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i+1}^{n+1} \binom{n+1}{j} \right) + \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=0}^{i} \binom{n+1}{j} \right) = \\ &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=i+1}^{n+1} \binom{n+1}{j} + \binom{n}{i} \sum_{j=0}^i \binom{n+1}{j} \right) = \\ &=& \sum_{i=0}^n \left( \binom{n}{i} \sum_{j=0}^{n+1} \binom{n+1}{j} \right) = \sum_{i=0}^n \left( \binom{n}{i} 2^{n+1} \right) = 2^{n+1} \sum_{i=0}^n \binom{n}{i} = 2^{n+1} \cdot 2^n = 2^{2n+1}. \end{eqnarray*}$$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).
- 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).
- 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).
- 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\).
Statistics:
71 students sent a solution. 6 points: 64 students. 5 points: 2 students. 4 points: 2 students. 2 points: 1 student. 1 point: 1 student. 0 point: 1 student.
Problems in Mathematics of KöMaL, December 2020