Uzasadnij tożsamości

[iks2011]

Uzasadnij tożsamości:
a) \(\displaystyle{ \sum_{k=1}^{n} {n \choose k} k(-1)^{k-1} = 0^{n-1}}\)
b) \(\displaystyle{ \sum_{k=2}^{n}k(k-1) {n \choose k} = n(n-1) 2^{n-2}}\)
c) \(\displaystyle{ \sum_{i=0}^{k} {m \choose i} {n \choose k-i} = {n+m \choose k}}\)
d) \(\displaystyle{ \sum_{i=0}^{k} {n \choose i} {n-i \choose k-i} = 2^{k} {n \choose k}}\)

Jak się brać za takie rzeczy? Wiem, co to jest suma, znam symbol Newtona, a jakoś i tak nic mi nie wychodzi... Próbuję najpierw do lewej i prawej strony podstawiać \(\displaystyle{ n = 1}\), potem \(\displaystyle{ n = n + 1}\) i przeważnie zacinam się przy rozwijaniu symbolu Newtona...

[Vardamir]

Indukcyjnie tak najczęściej udowadnia się takie tożsamości. Pokaż, gdzie się zacinasz w pierwszym.

Można też zauważyć jakiś trick. Choć do tego potrzebna jest pewna wprawa.

[iks2011]

Najpierw \(\displaystyle{ n = 1}\) - ok, wszystko się zgadza, \(\displaystyle{ 1 = 1}\).
Nie wiem teraz, jak właściwie wstawiać do tego całego równania \(\displaystyle{ n + 1}\) i rozwijać z nim sumę..

[Qń]

Indukcyjnie tak najczęściej udowadnia się takie tożsamości.

Nie no, skąd - trzy ostatnie tożsamości to typowe zadania na interpretację kombinatoryczną.

Tylko pierwsza tożsamość jest inna, ale i tu indukcja nie jest potrzebna - wystarczy skorzystać z tożsamości \(\displaystyle{ k\binom nk = n\binom{n-1}{k-1}}\) i z dwumianu Newtona. Ewentualnie wersja alternatywna dla zaawansowanych: zanegować górny indeks.

Q.