I sidste indlæg skrev jeg, at vi som det næste ville følge op på differentiation af polynomier, og vise at reglen $$ (x^p)’ = px^{p-1} $$ holdt for generelle $$ p \in \mathbb{R} $$. Vi tager dog lige et sidespring først og vender tilbage til en af resultaterne, som vi blot brugte uden at tænke nærmere over det sidste gang. $$! (a+b)^n = \sum_{k=0}^n\binom{n}{k}a^{n-k}b^k, $$ hvor $$ a,b\in \mathbb{R} $$ og $$ n \in \mathbb{n} $$. Vi vil vise denne identitet.
Induktion
Siden vi gerne vil vise at identiteten holder for all naturlige tal $$ n $$, har vi faktisk uendeligt mange identiteter vi gerne vil vise. Det kan jo tage lang tid, hvis vi går til dem en for en, så vi vil bruge et trick; nemlig et induktionsbevis.
Princippet i induktion er ganske simpel. Vi viser første, at vores identitet holder for et lille $$ n $$, hvilket forhåbentlig ikke er så svært. Dette kaldes induktionsbasisen. Herefter vil vi antage at vores identitet holder for et ukendt $$ n $$ og så vise at i så fald må den også holde for $$ n + 1 $$. Dette kaldes induktionstrinnet.
Hvis vi nu vises at identiteten holder for fx $$ n = 2 $$ og dernest viser den anden del, så kan vi se, fordi $$ n = 2 $$ virkede, må $$ n+1 = 2+1 = 3 $$ også virke. Men så kan vi jo vælge $$ n = 3 $$, og derfor må det også virke for $$ n +1 = 4 $$; osv…. Det er som dominobrikker der vælter og altid tager den næste med. Således får vi at identiteten holder for alle naturlige tal $$ n $$.
Bevis
Så lad os komme i gang.
Induktionsbasis
Jeg foreslog $$ n =2 $$ i eksemplet herover, men $$ n = 1 $$ er faktisk nok her. Dog synes jeg, at det er fint, hvis vi tjekker begge dele. Vi for brug for følgende $$! \begin{aligned} \binom{n}{0} &= \frac{n!}{0!(n-0)!} = \frac{n!}{n!} = 1 \\ \binom{n}{n} &=\frac{n!}{n!(n-n)!} = \frac{1}{0!} = 1 \end{aligned}. $$
For $$ n = 1 $$ har vi $$! \begin{aligned}(a+b)^1 = a+b &= \sum_{k=0}^1\binom{1}{k}a^{1-k}b^k \\ &= \binom{1}{0}a^1b^0 + \binom{1}{1}a^0b^1 = a + b. \end{aligned} $$
For $$ n = 2 $$ har vi via kvadratsætningen $$! (a+b)^2 = a^2 + 2ab + b^2 = \binom{2}{0}a^2b^0 + 2a^1b^1 + \binom{2}{2}a^0b^2. $$ Det eneste vi bør tjekke er om $$ 2 = \binom{2}{1} = \frac{2!}{1!(2-1)!}$$? Hvilket vi klart ser!
Induktionstrin
Vi antager nu at identiteten faktisk holder for et naturligt tal $$ n $$. Det her er den svære del: Nu gælder der de følgende udledninger. Læg mærke til at i første linie benytter vi vores antagelse til at omskrive $$ (a+b)^n $$. $$! \begin{aligned} (a+b)^{n+1} &= (a+b)(a+b)^n = (a+b)\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k \\ &= a\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k + b\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k \\ &= \sum_{k=0}^n\binom{n}{k}a^{(n+1)-k}b^k + \sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k+1} \\ &= a^{n+1} + \sum_{k=1}^n\binom{n}{k}a^{(n+1)-k}b^k \\ &\qquad\quad\, + \sum_{k=0}^{n-1}\binom{n}{k}a^{n-k}b^{k+1} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^{n}\binom{n}{k}a^{(n-1)-k}b^{k} \\ &\qquad\quad\, + \sum_{k=1}^n\binom{n}{k-1}a^{(n+1)-k}b^{k} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^n\left[\binom{n}{k} + \binom{n}{k-1}\right]a^{(n+1)-k}b^{k} + b^{n+1} \\ &= \sum_{k=0}^{n+1}\binom{n+1}{k}a^{(n+1)-k}b^{k}. \end{aligned} $$
Dermed har vi vist at identiteten holder. I den sidste lighed brugte vi følgende identitet $$! \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}. $$ Den viser vi nu $$! \begin{aligned} \binom{n}{k} + \binom{n}{k-1} &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!} \\ &= \frac{n!}{(k-1)!(n-k)!}\left[\frac{1}{k} + \frac{1}{n-k+1}\right] \\ &= \frac{n!}{(k-1)!(n-k)!}\left[\frac{n+1}{k(n-k+1)}\right] \\ &= \frac{(n+1)!}{k!(n-k+1)!} \\ &= \frac{(n+1)!}{k!((n+1)-k)!} = \binom{n+1}{k} \end{aligned} $$ Vi brugte her nogle tricks; fx benyttede vi at $$ k! = k\cdot (k-1)! $$ og ligeledes $$ (n-(k-1))! = (n-k+1)! = (n-k+1)\cdot (n-k)! $$ til at kunne tage $$ (k-1)! $$ og $$ (n-k)! $$ ud af en parentes i første linie. Fra linie 3 til 4 lavede vi så det modsatte trick for at samle faktorerne igen.
Konklusion
Vi har hermed vist at identiteten holder for alle naturlige tal $$ n $$.