Oppgave: Vis at [tex]{n \choose 0}-{n \choose 1}+{n \choose 2}-...+(-1)^k{n \choose k}=(-1)^k{n-1 \choose k}[/tex] ved å betrakte koeffisienten til [tex]x^k[/tex] på begge sider av identiteten [tex](1+x)^{n-1}=(1+x)^n(1+x)^{-1}[/tex]. (Oppg. 1.11c s. 17 i A First Course in Discrete Mathematics.)
Skriver [tex]\sum\limits_{r = 0}^{n-1} {x^{n-1}}{n-1 \choose r} =\frac{{n \choose 0}+{n \choose 1}x+{n \choose 2}x^2+...+{n \choose n}x^n}{1+x}[/tex].
Koeffisienten til [tex]x^k[/tex] på venstresiden er [tex]k\choose k+1[/tex].
På høyresiden ser det ut til at jeg må bruke polynomdivisjon for å få svaret. Det går galt (får ikke til å gjengi den her). Hva gjør jeg?
Diskret matematikk - finn koeffisient til x^k
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Solar Plexsus
- Over-Guru
- Innlegg: 1686
- Registrert: 03/10-2005 12:09
For det første er
[tex](1) \;\; (1+x)^{n-1} = \sum_{k=0}^{n-1} {n-1 \choose k} x^k.[/tex]
For det andre er
[tex]\frac{1}{1 + x} = \frac{1}{1 - (-x)} = \sum_{j=0}^{\infty} (-x)^j[/tex]
når [tex] |x|<1.[/tex] Følgelig blir
[tex](2) \;\; (1+x)^n \cdot (1+x)^{-1} = \sum_{i=0}^n {n \choose i} x^i \cdot \sum_{j=0}^{\infty} (-x)^j = \sum_{i=0}^n \sum_{j=0}^{\infty} {n \choose i} \cdot (-1)^j \cdot x^{i+j},[/tex]
hvilket betyr at koeffisienten til [tex]x^k[/tex] i (2) blir
[tex]\sum_{i=0}^k {n \choose i} \cdot (-1)^{k-i}[/tex].
Koeffisienten til [tex]x^k[/tex] i (1) er [tex]{n-1 \choose k}[/tex], så
[tex](3) \;\; \sum_{i=0}^k {n \choose i} \cdot (-1)^{k-i} = {n-1 \choose k}[/tex].
Ved å multiplisere begge sider av (3) med [tex](-1)^k[/tex], blir resultatet
[tex]\sum_{i=0}^k {n \choose i} \cdot (-1)^i = (-1)^k{n-1 \choose k}[/tex]
ettersom
[tex](-1)^k \cdot (-1)^{k-i} = (-1)^{i + 2(k-i)} = (-1)^i \cdot ((-1)^2)^{k-i} = (-1)^i \cdot 1^{k-i} = (-1)^i[/tex].
[tex](1) \;\; (1+x)^{n-1} = \sum_{k=0}^{n-1} {n-1 \choose k} x^k.[/tex]
For det andre er
[tex]\frac{1}{1 + x} = \frac{1}{1 - (-x)} = \sum_{j=0}^{\infty} (-x)^j[/tex]
når [tex] |x|<1.[/tex] Følgelig blir
[tex](2) \;\; (1+x)^n \cdot (1+x)^{-1} = \sum_{i=0}^n {n \choose i} x^i \cdot \sum_{j=0}^{\infty} (-x)^j = \sum_{i=0}^n \sum_{j=0}^{\infty} {n \choose i} \cdot (-1)^j \cdot x^{i+j},[/tex]
hvilket betyr at koeffisienten til [tex]x^k[/tex] i (2) blir
[tex]\sum_{i=0}^k {n \choose i} \cdot (-1)^{k-i}[/tex].
Koeffisienten til [tex]x^k[/tex] i (1) er [tex]{n-1 \choose k}[/tex], så
[tex](3) \;\; \sum_{i=0}^k {n \choose i} \cdot (-1)^{k-i} = {n-1 \choose k}[/tex].
Ved å multiplisere begge sider av (3) med [tex](-1)^k[/tex], blir resultatet
[tex]\sum_{i=0}^k {n \choose i} \cdot (-1)^i = (-1)^k{n-1 \choose k}[/tex]
ettersom
[tex](-1)^k \cdot (-1)^{k-i} = (-1)^{i + 2(k-i)} = (-1)^i \cdot ((-1)^2)^{k-i} = (-1)^i \cdot 1^{k-i} = (-1)^i[/tex].