Witam!
Jaki może być dowód kombinatoryczny do równania:
\(\displaystyle{ n+1\choose k}\) = \(\displaystyle{ n\choose k}\) +\(\displaystyle{ n-1\choose k-1}\) + \(\displaystyle{ n-2\choose k-2}\) + ... + \(\displaystyle{ n-k\choose k-k}\)
z góry dziękuje za wszelakie zainteresowanie tematem
pzdr
dowód kombinatoryczny
dowód kombinatoryczny
\(\displaystyle{ n+1 \choose k}\) to ilość sposobów wyboru k elementów ze zbioru n+1 elementowego. Zaznaczmy teraz w zbiorze n+1 elementowym, pewien element nazwijmy go A. Liczba wyborów opisanych wcześniej jest równa sumie liczby wyborów k elementów ze zbioru n(wszystkie podzbiory k elementowe bez A) oraz k-1 elementów ze zbioru n elementowego (zakładamy że A jest już wybrany wiec pozostaje nam wybrać k-1).
Mamy więc:
\(\displaystyle{ {n+1 \choose k} = + {n \choose k-1}}\)
Analogicznie wnioskujemy dla \(\displaystyle{ n \choose k-1}\) i kolejnych otrzymanych składników. W ten sposób rozwijamy sumę do żądanej postaci.
\(\displaystyle{ {n+1 \choose k}={n \choose k} + {n \choose k-1}={n \choose k} + {n-1 \choose k-1}+{n-1 \choose k-2}=\ldots={n\choose k} +{n-1\choose k-1} + {n-2\choose k-2} + ... + {n-k\choose k-k}}\)
Mamy więc:
\(\displaystyle{ {n+1 \choose k} = + {n \choose k-1}}\)
Analogicznie wnioskujemy dla \(\displaystyle{ n \choose k-1}\) i kolejnych otrzymanych składników. W ten sposób rozwijamy sumę do żądanej postaci.
\(\displaystyle{ {n+1 \choose k}={n \choose k} + {n \choose k-1}={n \choose k} + {n-1 \choose k-1}+{n-1 \choose k-2}=\ldots={n\choose k} +{n-1\choose k-1} + {n-2\choose k-2} + ... + {n-k\choose k-k}}\)