Strona 1 z 1
Dowód kombinatoryczny z symbolem Newtona
: 09 maja 2021, 20:41
autor: Przemo356
Hej. Czy ktoś umiałby udowodnić ten wzór kombinatorycznie i wytłumaczyć mniej więcej jak to zrobił ? To w nawiasach to symbol Newtona
\[ \sum_{k=0}^{r} {n+k\choose k} = {n+r+1\choose r} \]
Re: Dowód kombinatoryczny z symbolem Newtona
: 09 maja 2021, 21:49
autor: kerajs
\(P={n+r+1\choose r} ={n+r\choose r-1} +{n+r\choose r} ={n+r-1\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\={n+r-2\choose r-3}+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=...=\\
={n+2\choose 1}+{n+2\choose 2}+...+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\={n+1\choose 0}+{n+1\choose 1}+{n+2\choose 2}+...+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\
1+{n\choose 0}+{n+1\choose 1}+{n+2\choose 2}+...+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\=
1+\sum_{k=0}^{r} {n+k\choose k} \neq L\)
Re: Dowód kombinatoryczny z symbolem Newtona
: 09 maja 2021, 22:30
autor: panb
kerajs pisze: ↑09 maja 2021, 21:49
\(P={n+r+1\choose r} ={n+r\choose r-1} +{n+r\choose r} ={n+r-1\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\={n+r-2\choose r-3}+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=...=\\
={n+2\choose 1}+{n+2\choose 2}+...+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\={n+1\choose 0}+{n+1\choose 1}+{n+2\choose 2}+...+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\
1+{n\choose 0}+{n+1\choose 1}+{n+2\choose 2}+...+{n+r-2\choose r-2} +{n+r-1\choose r-1}+{n+r\choose r}=\\=
1+\sum_{k=0}^{r} {n+k\choose k} \neq L\)
\({n+1\choose 0}\neq 1+{n\choose0}\\
{n+1\choose 0} = {n\choose0}\)
Tym sposobem wzór jest udowodniony.