Udowodnij kombinatorycznie, że dla dowolnej liczby naturalnej \(\displaystyle{ n}\) zachodzi tożsamość:
\(\displaystyle{ \sum_{k=0}^{n} \sum_{j=0}^{n} {k \choose j} {n-k \choose j}= \sum_{m=0}^{n} {n+1 \choose 2m+1}}\)
Proszę o sprawdzenie poniższego rozwiązania:
Prawa strona równości to po prostu ilość podzbiorów o nieparzystej liczbie elementów zbioru \(\displaystyle{ n+1}\) elementowego. Mamy więc zbiór \(\displaystyle{ n+1}\) elementowy liczb naturalnych od \(\displaystyle{ 1}\) do \(\displaystyle{ n+1}\). Żeby zinterpretować lewą stronę podzielmy nasz zbiór \(\displaystyle{ n+1}\), elementowy na trzy grupy. Ustalmy jakieś \(\displaystyle{ k \in \left\{ 1,2,...,n+1\right\}}\). Pierwsza grupa to zbiór elementów mniejszych od \(\displaystyle{ k}\), druga grupa to element \(\displaystyle{ k}\) i trzecia grupa to elementy większe od \(\displaystyle{ k}\). Teraz z pierwszej grupy będziemy wybierać \(\displaystyle{ j}\) elementów. Do nich będziemy dorzucać element środkowy \(\displaystyle{ k}\) i do tej grupy będziemy jeszcze dorzucać \(\displaystyle{ j}\) elementów z trzeciej grupy. W efekcie dostaniemy zbiór \(\displaystyle{ 2j+1}\) elementowy i będzie to jeden z podzbiorów wyjściowego zbioru \(\displaystyle{ n+1}\) elementowego. \(\displaystyle{ j}\) przebiega wszystkie liczby od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\), czyli w ten sposób otrzymamy wszystkie zbiory jedno, trzy,pięcio,...,itd. elementowe zawierające środkowy element \(\displaystyle{ k}\). A \(\displaystyle{ k}\) przebiega wszystkie liczby od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\), zatem z uwagi na środkowy element dostaniemy w sumie ilość podzbiorów o nieparzystej liczbie elementów zbioru \(\displaystyle{ n+1}\) elementowego. Czy tak jest dobrze?