matematikk.net

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?

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