Kombinatorikk bevis

[KjetilEn]

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?

[sEirik]

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].

[ingentingg]

Start med høyresiden og vis venstresiden. Er generelt lettere å sette på felles brøkstrek enn å gå andre veien.

[KjetilEn]

[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

[dischler]

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