dowód indukcyjny

[tukanik]

Udowodnij, że:
\(\displaystyle{ {n +k -1 \choose k - 1 } = { k \choose 0 } { n - 1 \choose k - 1} +{ k \choose 1 } { n - 1 \choose k - 2} + { k \choose 2 } { n - 1 \choose k - 3} + ....+ { k \choose k-1 } { n - 1 \choose 0}}\)
Chciałbym, abyście mi pomogli przeprowadzić dowód indukcyjny tego czegoś. Nie chcę, żebyście robili to za mnie, a pchnęli mnie- jest to pierwsza indukcja przy dwóch zmiennych.

[Qń]

To szczególny przypadek tożsamości Cauchy'ego-Vandermonde'a i dużo prostszy od indukcji jest dowód kombinatoryczny.

Q.

[tukanik]

to może na przykładzie tego:
\(\displaystyle{ { n \choose 0 }{ n \choose k } + { n \choose 1 } { n-1 \choose k-1 } + {n \choose 2 } {n -2 \choose k -2 } + ...+ { n \choose k }{ n-k \choose 0 )} = 2^k { n \choose k }}\)

[Qń]

Tu również najprostszy jest dowód kombinatoryczny.

Mamy \(\displaystyle{ n}\) nosorożców i \(\displaystyle{ k}\) z nich zapisujemy do szkoły baletowej, a spośród zapisanych niektórym chcemy przyznać stypendium ministra kultury (być może wszystkim, być może żadnemu). Po obu stronach równości mamy na różne sposoby policzoną liczbę możliwości zrobienia tego.

Q.

[tukanik]

dobrze, to podaj mi proszę przykład, w którym będę mógł posłużyć się indukcją .