Delmengder
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
For to naturlige tall [tex]n[/tex] og [tex]r[/tex] der [tex] 1 \leq r \leq n[/tex], la [tex]S=\{ 1, 2, \ldots , n \}[/tex] være mengden av de naturlige tallene ikke større enn [tex]n[/tex]. I hver delmengde av [tex]S[/tex] med nøyaktig [tex]r[/tex] elementer, velg det minste tallet og ta det aritmetiske snittet av disse. Vis at dette blir lik [tex]\frac {n+1} {r+1}[/tex].
Ikke en veldig pen løsning, menmen:
Vi ser først at det åpenbart stemmer for [tex]r=1[/tex], da [tex]\frac{\sum_{k=1}^n k}{n}=\frac{n+1}{r+1}[/tex].
Dessuten stemmer det åpenbart for [tex]r=n[/tex], da eneste minste element i en delmengde er 1, og det opptrer 1 gang, og vi har da likhet.
Antall delmengder med [tex]r[/tex] elementer er [tex]{n \choose r}[/tex]. Enhver delmengde har et minste element, så summen av alle delmengder med k som minste element for [tex]1 \leq k \leq n+1-r[/tex] er [tex]{n \choose r}[/tex], dvs at
[tex]\sum^{n+1-r}_{k=1} {n-k \choose r-1} = {n \choose r}[/tex]
Vi må vise at det aritmetiske snittet av alle minste elementer er lik [tex]\frac{n+1}{r+1}[/tex], dvs
[tex]\frac{\sum^{n+1-r}_{k=1} {n-k \choose r-1}k}{{n \choose r}} = \frac{n+1}{r+1}[/tex]
eller
[tex]\sum^{n+1-r}_{k=1} {n-k \choose r-1}k = {n \choose r} \frac{n+1}{r+1}[/tex]
for alle [tex]1 \leq r \leq n.[/tex]
Anta dette stemmer for alle [tex]t<n[/tex]. Vi vil vise at
[tex]\sum^{t+2-r}_{k=1} {t+1-k \choose r-1}k = {t+1 \choose r} \frac{t+2}{r+1} [/tex]
for alle [tex]1 \leq r \leq t+1[/tex]. For [tex]r=1[/tex] og [tex]r=t+1[/tex] har vi allerede at likheten stemmer, så vi kan anta at [tex]2 \leq r \leq t[/tex].
Nå er
[tex]\sum^{t+2-r}_{k=1} {t+1-k \choose r-1}k = (t+2-r)+\sum^{t+1-r}_{k=1} \left( {t-k \choose r-1} + {t-k \choose r-2} \right) k = \\ (t+2-r) + \sum^{t+1-r}_{k=1} {t-k \choose r-1}k + \sum^{t+1-(r-1)}_{k=1}{t-k \choose (r-1)-1}k-{t-(n+1-(r-1)) \choose (r-1)-1}(t+1-(r-1)) = \\ {t \choose r} \frac{t+1}{r+1}+ {t \choose r-1} \frac{t+1}{r} = \frac{t+1}{r(r+1)}\left( r{t \choose r}+(r+1){t \choose r-1} \right) = \frac{t+1}{r(r+1)} \left( {t+1 \choose r}+{t \choose r-1} \right) = \\ {t+1 \choose r} \left( \frac{t+1}{r(r+1)}+\frac{t+1}{r(r+1)}\frac{r}{t+1} \right) = {t+1 \choose r} \frac{t+2}{r+1}[/tex].
Det stemmer det åpenbart for [tex]n=1[/tex]. Så ved induksjon gjelder ulikheten for alle [tex]n[/tex].
Vi ser først at det åpenbart stemmer for [tex]r=1[/tex], da [tex]\frac{\sum_{k=1}^n k}{n}=\frac{n+1}{r+1}[/tex].
Dessuten stemmer det åpenbart for [tex]r=n[/tex], da eneste minste element i en delmengde er 1, og det opptrer 1 gang, og vi har da likhet.
Antall delmengder med [tex]r[/tex] elementer er [tex]{n \choose r}[/tex]. Enhver delmengde har et minste element, så summen av alle delmengder med k som minste element for [tex]1 \leq k \leq n+1-r[/tex] er [tex]{n \choose r}[/tex], dvs at
[tex]\sum^{n+1-r}_{k=1} {n-k \choose r-1} = {n \choose r}[/tex]
Vi må vise at det aritmetiske snittet av alle minste elementer er lik [tex]\frac{n+1}{r+1}[/tex], dvs
[tex]\frac{\sum^{n+1-r}_{k=1} {n-k \choose r-1}k}{{n \choose r}} = \frac{n+1}{r+1}[/tex]
eller
[tex]\sum^{n+1-r}_{k=1} {n-k \choose r-1}k = {n \choose r} \frac{n+1}{r+1}[/tex]
for alle [tex]1 \leq r \leq n.[/tex]
Anta dette stemmer for alle [tex]t<n[/tex]. Vi vil vise at
[tex]\sum^{t+2-r}_{k=1} {t+1-k \choose r-1}k = {t+1 \choose r} \frac{t+2}{r+1} [/tex]
for alle [tex]1 \leq r \leq t+1[/tex]. For [tex]r=1[/tex] og [tex]r=t+1[/tex] har vi allerede at likheten stemmer, så vi kan anta at [tex]2 \leq r \leq t[/tex].
Nå er
[tex]\sum^{t+2-r}_{k=1} {t+1-k \choose r-1}k = (t+2-r)+\sum^{t+1-r}_{k=1} \left( {t-k \choose r-1} + {t-k \choose r-2} \right) k = \\ (t+2-r) + \sum^{t+1-r}_{k=1} {t-k \choose r-1}k + \sum^{t+1-(r-1)}_{k=1}{t-k \choose (r-1)-1}k-{t-(n+1-(r-1)) \choose (r-1)-1}(t+1-(r-1)) = \\ {t \choose r} \frac{t+1}{r+1}+ {t \choose r-1} \frac{t+1}{r} = \frac{t+1}{r(r+1)}\left( r{t \choose r}+(r+1){t \choose r-1} \right) = \frac{t+1}{r(r+1)} \left( {t+1 \choose r}+{t \choose r-1} \right) = \\ {t+1 \choose r} \left( \frac{t+1}{r(r+1)}+\frac{t+1}{r(r+1)}\frac{r}{t+1} \right) = {t+1 \choose r} \frac{t+2}{r+1}[/tex].
Det stemmer det åpenbart for [tex]n=1[/tex]. Så ved induksjon gjelder ulikheten for alle [tex]n[/tex].
Ser bra ut dette. En mer kombinatorisk løsning begynner som du har gjort ved å innse at vi må vise at [tex]\sum_{k=1} ^n k {n-k \choose r-1} = \frac {n+1} {r+1} {n \choose r} = {n+1 \choose r+1}[/tex], der vi av latskap definerer [tex]a \choose b = 0[/tex] om [tex]b>a[/tex]. Så ser vi at høyresiden kan sees på som antallet måter man kan plukke ut et fotballag på [tex]r+1[/tex] spillere fra en gruppe på [tex]n+1[/tex] personer på. La personene være nummerert fra [tex]1[/tex] til [tex]n+1[/tex]. På venstresiden er et ledd i summen antallet måter vi kan plukke ut et fotballag der vi tar med den [tex]k+1[/tex]-te personen, nøyaktig én av personene med nummer lavere enn ham, og fyller opp gruppen med [tex]r-1[/tex] personer fra de [tex](n+1)-(k+1) = n-k[/tex] personene med nummer høyere enn ham.
Vi ser at ethvert mulig fotballag kun telles én gang på denne måten, og intet lag telles to ganger (da 'hvilket ledd laget tilhører' er unikt bestemt av de to personene i laget med lavest nummer), så om vi summerer dette fra [tex]k=1[/tex] til [tex]k=n[/tex] (eller egentlig [tex]k=n+1-r[/tex]) må vi få antallet mulige måter å velge ut fotballag på, som som nevnt tidligere er lik [tex]{n+1 \choose r+1}[/tex] og derfor har vi at venstresiden og høyresiden er like.
Vi ser at ethvert mulig fotballag kun telles én gang på denne måten, og intet lag telles to ganger (da 'hvilket ledd laget tilhører' er unikt bestemt av de to personene i laget med lavest nummer), så om vi summerer dette fra [tex]k=1[/tex] til [tex]k=n[/tex] (eller egentlig [tex]k=n+1-r[/tex]) må vi få antallet mulige måter å velge ut fotballag på, som som nevnt tidligere er lik [tex]{n+1 \choose r+1}[/tex] og derfor har vi at venstresiden og høyresiden er like.