Udowodnij tożsamość k · (n po k) = n · (n − 1 po k − 1) - dwa dowody

Krok 1. Sprawdzamy na liczbach. Dla $n = 10$, $k = 3$: lewa strona to $3 \cdot \binom{10}{3} = 3 \cdot 120 = 360$, prawa $10 \cdot \binom{9}{2} = 10 \cdot 36 = 360$. Równość wygląda wiarygodnie - teraz dowód dla dowolnych $n$, $k$.

Krok 2. Dowód rachunkowy - lewa strona. Rozpisujemy symbol i skracamy $k$ z $k!$, korzystając z $k! = k \cdot (k-1)!$:

$k \cdot \binom{n}{k} = k \cdot \frac{n!}{k! \cdot (n-k)!} = \frac{n!}{(k-1)! \cdot (n-k)!}.$

Krok 3. Prawa strona. Zauważamy, że $(n-1) - (k-1) = n - k$, i korzystamy z $n \cdot (n-1)! = n!$:

$n \cdot \binom{n-1}{k-1} = n \cdot \frac{(n-1)!}{(k-1)! \cdot (n-k)!} = \frac{n!}{(k-1)! \cdot (n-k)!}.$

Obie strony są równe temu samemu wyrażeniu, co kończy dowód.

Krok 4. Dowód kombinatoryczny - liczymy jedno na dwa sposoby. Z grupy $n$ osób wybieramy $k$-osobową komisję i jej przewodniczącego (który należy do komisji).

• Sposób 1. Najpierw komisja - na $\binom{n}{k}$ sposobów, potem przewodniczący spośród jej $k$ członków - na $k$ sposobów. Razem $k \cdot \binom{n}{k}$.
• Sposób 2. Najpierw przewodniczący - na $n$ sposobów, potem pozostałych $k - 1$ członków spośród $n - 1$ osób - na $\binom{n-1}{k-1}$ sposobów. Razem $n \cdot \binom{n-1}{k-1}$.

Policzyliśmy ten sam zbiór dwiema metodami, więc wyniki muszą być równe.

Odpowiedź. Tożsamość jest prawdziwa dla wszystkich $1 \leq k \leq n$; obie strony są równe $\frac{n!}{(k-1)! \cdot (n-k)!}$, a kombinatorycznie liczą komisje $k$-osobowe z przewodniczącym.