Bevis identiteten:
[tex] \begin{pmatrix} n \\ \\ \\ \\ \\ \\ \\ \\ \\ r \end{pmatrix} = \begin{pmatrix} n -1 \\ \\ \\ \\ \\ \\ \\ \\ \\ r -1 \end{pmatrix} + \begin{pmatrix} n - 1 \\ \\ \\ \\ \\ \\ \\ \\ \\ r \end{pmatrix} \hspace9 , \hspace9(n \geq 1)[/tex]
Noen som har noen tips hvordan jeg burde starte?
Kombinatorikk bevis
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Start med definisjonen:
[tex]{n \choose r} = \frac{n!}{r! \cdot (n-r)!}[/tex]
Vi ser på første binomialkoeffisient, og får at
[tex]{n-1 \choose r-1} = \frac{(n-1)!}{(r-1)! \cdot ((n-1)-(r-1))!} = \frac{(n-1)!}{(r-1)! \cdot (n-r)!}[/tex]
Vi vet at [tex]a! = a \cdot (a-1)![/tex]. Derfor [tex]r! = r \cdot (r-1)![/tex]
Vi utvider brøken med r:
[tex]{n-1 \choose r-1} = \frac{r \cdot (n-1)!}{r \cdot (r-1)! \cdot (n-r)!}[/tex]
Setter inn:
[tex]{n-1 \choose r-1} = \frac{r \cdot (n-1)!}{r! \cdot (n-r)!}[/tex]
Vi ser på neste binomialkoeffisient:
[tex]{n-1 \choose r} = \frac{(n-1)!}{r! \cdot (n-r-1)!}[/tex]
Vi vet at [tex]a! = a \cdot (a-1)![/tex]. Derfor [tex](n-r)! = (n-r) \cdot (n-r-1)![/tex]
Vi utvider brøken med (n-r):
[tex]{n-1 \choose r} = \frac{(n-r) \cdot (n-1)!}{r! \cdot (n-r) \cdot (n-r-1)!}[/tex]
Setter inn:
[tex]{n-1 \choose r} = \frac{(n-r) \cdot (n-1)!}{r! \cdot (n-r)!}[/tex]
Vi legger dem sammen:
[tex]S = {n-1 \choose r-1} + {n-1 \choose r} = \frac{r \cdot (n-1)!}{r! \cdot (n-r)!} + \frac{(n-r) \cdot (n-1)!}{r! \cdot (n-r)!}[/tex]
Trekker sammen brøkene:
[tex]S = \frac{r \cdot (n-1)! + (n-r) \cdot (n-1!)}{r! \cdot (n-r)!}[/tex]
Faktoriserer teller:
[tex]S = \frac{(n-1)! \cdot (r + n - r)}{r! \cdot (n-r)!}[/tex]
Vi kan stryke:
[tex]S = \frac{(n-1)! \cdot (n)}{r! \cdot (n-r)!}[/tex]
Vi bruker at [tex](n-1)! \cdot n = n![/tex], og får
[tex]S = \frac{n!}{r! \cdot (n-r)!}[/tex]
Og vi har pr. definisjon at
[tex]S = {n \choose r}[/tex].
[tex]{n \choose r} = \frac{n!}{r! \cdot (n-r)!}[/tex]
Vi ser på første binomialkoeffisient, og får at
[tex]{n-1 \choose r-1} = \frac{(n-1)!}{(r-1)! \cdot ((n-1)-(r-1))!} = \frac{(n-1)!}{(r-1)! \cdot (n-r)!}[/tex]
Vi vet at [tex]a! = a \cdot (a-1)![/tex]. Derfor [tex]r! = r \cdot (r-1)![/tex]
Vi utvider brøken med r:
[tex]{n-1 \choose r-1} = \frac{r \cdot (n-1)!}{r \cdot (r-1)! \cdot (n-r)!}[/tex]
Setter inn:
[tex]{n-1 \choose r-1} = \frac{r \cdot (n-1)!}{r! \cdot (n-r)!}[/tex]
Vi ser på neste binomialkoeffisient:
[tex]{n-1 \choose r} = \frac{(n-1)!}{r! \cdot (n-r-1)!}[/tex]
Vi vet at [tex]a! = a \cdot (a-1)![/tex]. Derfor [tex](n-r)! = (n-r) \cdot (n-r-1)![/tex]
Vi utvider brøken med (n-r):
[tex]{n-1 \choose r} = \frac{(n-r) \cdot (n-1)!}{r! \cdot (n-r) \cdot (n-r-1)!}[/tex]
Setter inn:
[tex]{n-1 \choose r} = \frac{(n-r) \cdot (n-1)!}{r! \cdot (n-r)!}[/tex]
Vi legger dem sammen:
[tex]S = {n-1 \choose r-1} + {n-1 \choose r} = \frac{r \cdot (n-1)!}{r! \cdot (n-r)!} + \frac{(n-r) \cdot (n-1)!}{r! \cdot (n-r)!}[/tex]
Trekker sammen brøkene:
[tex]S = \frac{r \cdot (n-1)! + (n-r) \cdot (n-1!)}{r! \cdot (n-r)!}[/tex]
Faktoriserer teller:
[tex]S = \frac{(n-1)! \cdot (r + n - r)}{r! \cdot (n-r)!}[/tex]
Vi kan stryke:
[tex]S = \frac{(n-1)! \cdot (n)}{r! \cdot (n-r)!}[/tex]
Vi bruker at [tex](n-1)! \cdot n = n![/tex], og får
[tex]S = \frac{n!}{r! \cdot (n-r)!}[/tex]
Og vi har pr. definisjon at
[tex]S = {n \choose r}[/tex].
Sist redigert av sEirik den 02/03-2007 19:21, redigert 2 ganger totalt.
-
- Weierstrass
- Innlegg: 451
- Registrert: 25/08-2005 17:49
Start med høyresiden og vis venstresiden. Er generelt lettere å sette på felles brøkstrek enn å gå andre veien.
[tex]\frac{n!}{r!(n-r)!} = \frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-r-1)!}[/tex]
Utvider uttrykket
= [tex] \frac{(n-1)!}{(r-1)!(n-r)(n-r-1)!}+\frac{(n-1)!}{r(r-1)!(n-r-1)!}[/tex]
Setter på felles brøkstrek
= [tex]\frac{r(n-1)! + (n-r)(n-1)!}{(r-1)!(n-r-1)!r(n-r)}[/tex]
Kom hit først, men veien var jo ikke så lang videre. Kan bli blind på noen uttrykk noen ganger, så man ikke ser de enkleste løsninger
Forkorter i nevner
= [tex]\frac{r(n-1)! + (n-r)(n-1)!}{r!(n-r)!}[/tex]
Faktoriserer i teller
= [tex]\frac{(n-r+r)(n-1)!}{r!(n-r)!}[/tex]
Forkorter teller
= [tex]\frac{n(n-1)!}{r!(n-r)!}[/tex]
Og vips
= [tex]\frac{n!}{r!(n-r)!}[/tex]
Takker for ypperlig fasit sEirik
Utvider uttrykket
= [tex] \frac{(n-1)!}{(r-1)!(n-r)(n-r-1)!}+\frac{(n-1)!}{r(r-1)!(n-r-1)!}[/tex]
Setter på felles brøkstrek
= [tex]\frac{r(n-1)! + (n-r)(n-1)!}{(r-1)!(n-r-1)!r(n-r)}[/tex]
Kom hit først, men veien var jo ikke så lang videre. Kan bli blind på noen uttrykk noen ganger, så man ikke ser de enkleste løsninger
Forkorter i nevner
= [tex]\frac{r(n-1)! + (n-r)(n-1)!}{r!(n-r)!}[/tex]
Faktoriserer i teller
= [tex]\frac{(n-r+r)(n-1)!}{r!(n-r)!}[/tex]
Forkorter teller
= [tex]\frac{n(n-1)!}{r!(n-r)!}[/tex]
Og vips
= [tex]\frac{n!}{r!(n-r)!}[/tex]
Takker for ypperlig fasit sEirik
Et annet bevis:
venstreside: antall måter å plukke ut r elementer av n elementer (per def.).
høyreside: velg ut et element og splitt opp summen fra venstreside i to
1. de utvalg der dette elementet er med, noe du får ved å velge ut r-1 elementene fra de resterende n-1 elementene
2. de utvalg der dette elementet ikke er med som tilsvarer å velge alle r elementer fra de resterende n-1 elementene
Denne oppdelingen tilsvarer summen på høyresiden
venstreside: antall måter å plukke ut r elementer av n elementer (per def.).
høyreside: velg ut et element og splitt opp summen fra venstreside i to
1. de utvalg der dette elementet er med, noe du får ved å velge ut r-1 elementene fra de resterende n-1 elementene
2. de utvalg der dette elementet ikke er med som tilsvarer å velge alle r elementer fra de resterende n-1 elementene
Denne oppdelingen tilsvarer summen på høyresiden