Binomialsum
Lagt inn: 28/02-2009 11:29
Finn [tex]\sum_{k=0}^n k{2n\choose 2k}[/tex].
Godtas telling som bevis?
Side 1 av 1
Lagt inn: 28/02-2009 13:39
[tex]\sum_{k=0}^n k{2n\choose 2k}=n2^{2(n-1)}[/tex]
Godtas telling som bevis?
Godtas telling som bevis?
Lagt inn: 28/02-2009 13:49
La [tex]\,S=\sum_{k=0}^n k{2n\choose 2k}=0 \cdot {2n\choose 0}+1 \cdot {2n\choose 2}+2 \cdot {2n\choose 4}+ \cdots +n \cdot {2n\choose 2n}[/tex]
Men vi vet også at [tex]\, {n\choose k}={n\choose n-k}\,[/tex] og derfor har vi at:
[tex]\,S=\sum_{k=0}^n k{2n\choose 2n-2k}=0 \cdot {2n\choose 2n}+1 \cdot {2n\choose 2n-2}+2 \cdot {2n\choose 2n-4}+ \cdots +n \cdot{2n\choose 0}[/tex]
Plusser vi disse sammen får vi:
[tex]2S=n \left( {2n\choose 0}+ {2n\choose 2}+ {2n\choose 4}+ \cdots +{2n\choose 2n} \right)[/tex]
Vi har også at
[tex]0=(1-1)^{2n}=\sum_{k=0}^{2n} (-1)^k\cdot {2n\choose k}= {2n\choose 0}- {2n\choose 1}+ {2n\choose 2}- \cdots +{2n\choose 2n}[/tex]
Som gir at
[tex]{2n\choose 0}+ {2n\choose 2}+ {2n\choose 4}+ \cdots +{2n\choose 2n}={2n\choose 1}+ {2n\choose 3}+ {2n\choose 5}+ \cdots +{2n\choose 2n-1}[/tex]
Dette gir at
[tex]2S=n \left( {2n\choose 0}+ {2n\choose 2}+ {2n\choose 4}+ \cdots +{2n\choose 2n} \right)=n \left( \frac{{2n\choose 0}+ {2n\choose 1}+ {2n\choose 2}+ \cdots +{2n\choose 2n}}{2} \right)=n\frac{2^{2n}}{2}[/tex]
[tex]S=n2^{2n-2}[/tex]
Men vi vet også at [tex]\, {n\choose k}={n\choose n-k}\,[/tex] og derfor har vi at:
[tex]\,S=\sum_{k=0}^n k{2n\choose 2n-2k}=0 \cdot {2n\choose 2n}+1 \cdot {2n\choose 2n-2}+2 \cdot {2n\choose 2n-4}+ \cdots +n \cdot{2n\choose 0}[/tex]
Plusser vi disse sammen får vi:
[tex]2S=n \left( {2n\choose 0}+ {2n\choose 2}+ {2n\choose 4}+ \cdots +{2n\choose 2n} \right)[/tex]
Vi har også at
[tex]0=(1-1)^{2n}=\sum_{k=0}^{2n} (-1)^k\cdot {2n\choose k}= {2n\choose 0}- {2n\choose 1}+ {2n\choose 2}- \cdots +{2n\choose 2n}[/tex]
Som gir at
[tex]{2n\choose 0}+ {2n\choose 2}+ {2n\choose 4}+ \cdots +{2n\choose 2n}={2n\choose 1}+ {2n\choose 3}+ {2n\choose 5}+ \cdots +{2n\choose 2n-1}[/tex]
Dette gir at
[tex]2S=n \left( {2n\choose 0}+ {2n\choose 2}+ {2n\choose 4}+ \cdots +{2n\choose 2n} \right)=n \left( \frac{{2n\choose 0}+ {2n\choose 1}+ {2n\choose 2}+ \cdots +{2n\choose 2n}}{2} \right)=n\frac{2^{2n}}{2}[/tex]
[tex]S=n2^{2n-2}[/tex]
Lagt inn: 28/02-2009 14:30
Telling godtas som bevis hvis du bare kan argumentere greit for det.
Fin løsning, Zivert.
Fin løsning, Zivert.
Lagt inn: 28/02-2009 14:45
[tex] S=\sum_{k=0}^n k{2n\choose 2k}=0 \cdot {2n\choose 0}+1 \cdot {2n\choose 2}+2 \cdot {2n\choose 4}+ \cdots +n \cdot {2n\choose 2n}[/tex]
Det er vanskelig å tolke [tex]S[/tex] kombinatorisk, så vi ser på [tex]2S[/tex].
[tex] 2S=2 \cdot {2n\choose 2}+4 \cdot {2n\choose 4}+ \cdots +2n \cdot {2n\choose 2n}[/tex]
Dette er antall måter vi kan velge grupper på 2, 4,..., 2n personer fra en ansamling av 2n personer, og der vi i tillegg velger en gruppeleder. Vi prøver nå å telle dette. Nummerer de 2n personene fra 1 til 2n, og la en 2n-tuppel representere grupper vi kan lage av 2n personer. Vi gir tuppelen en indeks som bestemmer gruppelederen, og vi lar en j eller en n svare til om en person er med i gruppen eller ikke. Har vi for eksempel n=3, vil 6-tuppelen [tex](j,n,j,j,j,n)_5[/tex] betegne gruppen med person nr. 1, 3, 4 og 5, der 5 er gruppelederen.
Indeksen har klart 2n forskjellige muligheter, én for hver av personene. Da har vi allerede plassert en j, og antall muligheter for å plassere de andre j'ene vil være [tex]{2n-1\choose 1}+{2n-1\choose 3}+\cdots+{2n-1\choose 2n-1}=2^{2n-2}[/tex]
At summen blir dette kan man vise med binomialformelen.
[tex]2S=2n \cdot 2^{2n-2}[/tex]
[tex]S=n \cdot 2^{2n-2}[/tex]
Det er vanskelig å tolke [tex]S[/tex] kombinatorisk, så vi ser på [tex]2S[/tex].
[tex] 2S=2 \cdot {2n\choose 2}+4 \cdot {2n\choose 4}+ \cdots +2n \cdot {2n\choose 2n}[/tex]
Dette er antall måter vi kan velge grupper på 2, 4,..., 2n personer fra en ansamling av 2n personer, og der vi i tillegg velger en gruppeleder. Vi prøver nå å telle dette. Nummerer de 2n personene fra 1 til 2n, og la en 2n-tuppel representere grupper vi kan lage av 2n personer. Vi gir tuppelen en indeks som bestemmer gruppelederen, og vi lar en j eller en n svare til om en person er med i gruppen eller ikke. Har vi for eksempel n=3, vil 6-tuppelen [tex](j,n,j,j,j,n)_5[/tex] betegne gruppen med person nr. 1, 3, 4 og 5, der 5 er gruppelederen.
Indeksen har klart 2n forskjellige muligheter, én for hver av personene. Da har vi allerede plassert en j, og antall muligheter for å plassere de andre j'ene vil være [tex]{2n-1\choose 1}+{2n-1\choose 3}+\cdots+{2n-1\choose 2n-1}=2^{2n-2}[/tex]
At summen blir dette kan man vise med binomialformelen.
[tex]2S=2n \cdot 2^{2n-2}[/tex]
[tex]S=n \cdot 2^{2n-2}[/tex]