Suma symboli Newtona wzdłuż przekątnej trójkąta Pascala (reguła kija hokejowego)

Krok 1. Pomysł - zamieniamy pierwszy składnik. Ponieważ $\binom{2}{2} = 1 = \binom{3}{3}$, możemy zacząć sumę od $\binom{3}{3}$. Wtedy pierwsze dwa składniki są sąsiadami z wiersza $3$ i łączą się regułą Pascala $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$:

$\binom{3}{3} + \binom{3}{2} = \binom{4}{3}.$

Krok 2. Lawina. Wynik znów łączy się z kolejnym składnikiem:

$\binom{4}{3} + \binom{4}{2} = \binom{5}{3}, \qquad \binom{5}{3} + \binom{5}{2} = \binom{6}{3}, \qquad \ldots$

Każdy krok podnosi wiersz o jeden. Po dołączeniu ostatniego składnika $\binom{10}{2}$ dostajemy

$\binom{10}{3} + \binom{10}{2} = \binom{11}{3}.$

Na trójkącie Pascala liczby $\binom{2}{2}, \binom{3}{2}, \ldots, \binom{10}{2}$ leżą na jednej przekątnej, a ich suma stoi o wiersz niżej, „za zakrętem” - stąd angielska nazwa hockey stick.

Krok 3. Obliczamy.

$\binom{11}{3} = \frac{11 \cdot 10 \cdot 9}{3 \cdot 2 \cdot 1} = 165.$

Sprawdzenie wprost: $1 + 3 + 6 + 10 + 15 + 21 + 28 + 36 + 45 = 165$.

Krok 4. Dlaczego tak jest - interpretacja. Liczymy trzyelementowe podzbiory zbioru $\{1, 2, \ldots, 11\}$ według ich największego elementu $m$. Gdy największy jest $m$, dwa pozostałe elementy wybieramy spośród $1, \ldots, m-1$ na $\binom{m-1}{2}$ sposobów, przy czym $m = 3, 4, \ldots, 11$. Reguła dodawania daje dokładnie naszą sumę, a wszystkich takich podzbiorów jest $\binom{11}{3}$.

Odpowiedź. Suma jest równa $\binom{11}{3} = 165$.