Matematyka.pl

Witam, mógłby ktoś podrzucić ideę na tę tożsamość:
\(\displaystyle{ \sum_{j=0}^{k} {n \choose j} = \sum_{j=0}^{k} {n-j-1 \choose k-j} \cdot 2^{j}}\), \(\displaystyle{ 0 \le k \le n - 1}\)


Siedzę juz troche nad tym i nie moge wymyslic. Najlepiej by bylo gdyby ktos podrzucil pomysl na interpretacje kombinatoryczna.

Interpretacja musiałaby być bardzo wyszukana chyba.. Indukcja po \(\displaystyle{ n}\) i wychodzi bardzo ładnie - założenie jest takie, że dla danego \(\displaystyle{ n}\) i dowolnego (spełniającego założenia) \(\displaystyle{ k}\) równość zachodzi.

adambak pisze:Interpretacja musiałaby być bardzo wyszukana chyba..

Są takie metody z przesuwaniem i rozmnażaniem pionków na szachownicy w kształcie trójkąta Pascala. Może nie różni się to bardzo od indukcji, ale chyba jest uznawane jako interpretacja kombinatoryczna.

Wymyśliłem też jakąś uczciwszą interpretację, ale jest trochę udziwniona i okrutna. Załóżmy że mam \(\displaystyle{ n}\) dzieci. Co mogę zrobić z \(\displaystyle{ k}\) cukierkami, jeśli \(\displaystyle{ k<n}\)? Oczywiście mogę ich zjeść tyle, żeby się całkiem zasłodzić, a jeśli zostanie jeszcze \(\displaystyle{ j}\), to rozdam je dzieciom, każdemu po co najwyżej jednym. Zbiór obdarowanych dzieci mogę wybrać na \(\displaystyle{ \binom nj}\) sposobów.

Ale mogę też zrobić inaczej. Przywołuję po kolei dzieci. Jeśli przywołane dziecko odgadnie zagadkę, to dostaje cukierka (gdy już nie mam cukierków to jako zagadkę daję dowód jakiegoś otwartego problemu). Niech \(\displaystyle{ j}\) będzie najmniejszą taką liczbą, że gdy zostało mi jeszcze \(\displaystyle{ j}\) dzieci, to wiedziałem że mogę już zadawać same łatwe zagadki. Przy ustalonym \(\displaystyle{ j}\) liczba możliwych zbiorów obdarowanych dzieci jest równa \(\displaystyle{ \binom{n-j-1}{k-j} \cdot 2^{j}}\), bo pierwszym \(\displaystyle{ n-j-1}\) dzieciom dałem \(\displaystyle{ k-j}\) cukierków, dziecko \(\displaystyle{ n-j}\) nie dostało cukierka, a każde następne mogło dostać albo nie.