Matematyka.pl

Stosując argumentację kombinatoryczną, udowodnić tożsamość: \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} (m-1) ^{n-k}= m^{n}}\)

Zliczamy funkcje ze zbioru \(\displaystyle{ \{ 1,2, \ldots , n\}}\) w zbiór \(\displaystyle{ \{ 1,2, \ldots , m\}}\).

Z lewej strony najpierw wybieramy \(\displaystyle{ k}\) argumentów, które przejdą na jedynkę, a pozostałych \(\displaystyle{ n-k}\) przechodzi na dowolną liczbę różną od jedynki. Oczywiście \(\displaystyle{ k}\) może przyjmować wartości od \(\displaystyle{ 0}\) (gdy jedynka nie należy do zbioru wartości funkcji) do \(\displaystyle{ n}\) (dla funkcji stale równej jeden).

Q.

ja to zrobiłam tak:
\(\displaystyle{ (m+x) ^{n}= \sum_{k=0}^{n} {n \choose k} m ^{n-k}x ^{k}}\)
następnie przyjęłam, że x=1 i wyszło mi:
\(\displaystyle{ (m+1) ^{n}= \sum_{k=0}^{n} {n \choose k} m ^{n-k}}\)
i nie wiem co dalej...

Wystarczyłoby teraz zamiast \(\displaystyle{ m}\) wstawić \(\displaystyle{ m-1}\), ale oczywiście nie jest to argumentacja kombinatoryczna o którą proszono.

Q.

racja
dziękuję