Bevisa binominalsatsen m.h.a induktion

Hej, Pluggakuten!

För ett tag sedan gick vi igenom binominalsatsen, men jag blev inte riktigt övertygad av det kombinatoriska "beviset". Därför vill jag bevisa formeln för mig själv med induktion. Binominalsatsen lyder som bekant:

$\displaystyle (a+b)^{n}=\sum_{k=0}^{ n}\binom{n}{k}·a^{n-k}·b^{k}$ .

Det verkar logiskt att köra induktion över den övre gränsen, alltså $n$ , men jag vet inte riktigt hur jag ska ta mig vidare med min ansats. Basfallet är trivialt så jag kommer inte skriva upp det. Men vi vet enligt induktionsantagandet att:

$\displaystyle (a+b)^{m}=\sum_{k=0}^{ m}\binom{m}{k}·a^{m-k}·b^{k}\Leftrightarrow (a+b)^{m+1}=(a+b)\sum_{k=0}^{ m}\binom{m}{k}·a^{m-k}·b^{k}$ .

Det som då ska visas med hjälp av induktionsantagandet är att:

$\displaystyle (a+b)^{m+1}=\sum_{k=0}^{ m+1}\binom{m+1}{k}·a^{m-k+1}·b^{k}$ , med andra ord att:

$\displaystyle (a+b)\sum_{k=0}^{ m}\binom{m}{k}·a^{m-k}·b^{k}=\sum_{k=0}^{ m+1}\binom{m+1}{k}·a^{m-k+1}·b^{k}$ .

Jag ser att det är möjligt att bryta ut en faktor $a$ ur den högra summan, som är oberoende av summan. Dessutom har jag försökt fiffla lite med faktorn $\displaystyle \binom{m}{k}$ för att försöka få den att se mer lika varandra ut i de olika summorna, men utan att komma någonstans.

Har ni några bra förslag på hur jag kan försöka visa likheten ovan?

Försökte skissa på en lösning, nådde inte riktigt fram men en tanke är väl att du ska få summorna att summera till samma index. Bryt därmed ut sista termen ur den högre summan. Därefter vill du skriva ut "m över k" i deras definitioner uttryckt i fakulteter, detta gör det lättare att jobba med dem. Därefter är det bara att fortsätta pilla tills VL och HL ser likadana ut.

Tack för ditt svar! Jag hade faktiskt redan testat att skriva om summan så att indexen blev samma, och då fick jag att det som ska visas är:

$\displaystyle a\sum_{k=0}^{m}[\frac{m!}{(m-k)!k!}·a^{m-k}·b^{k}]+b\sum_{k=0}^{m}[\frac{m!}{(m-k)!k!}·a^{m-k}·b^{k}]$

$\displaystyle =a\sum_{k=0}^{m}[\frac{m!}{(m-k)!k!}·\frac{m+1}{m+1-k}·a^{m-k}·b^{k}]+b^{m+1}$

Det finns ju många saker som är suspekt lika här mellan vänster- och högerledet, och det känns som jag bara missar någon detalj eller något. Några tipps hur jag kan ta mig härifrån?

Det stora problemet är den där dumma faktorn $\displaystyle \frac{m+1}{m+1-k}$ i högerledet. Jag vet inte hur jag ska "få in" den i vänsterledet.

Jag inser nu att det är någonting här som inte riktigt stämmer. Det ena ledet spottar ut $\displaystyle a (a^2 + 3 a b + 6b^2) + b^3$ medan det andra spottar ut $\displaystyle a (a^2 + 3 a b + 3 b^2) + b^3$ för m=2. Märkligt. De är suspekt nära varandra. Vad är det jag har gjort fel här?:

Efter att ha "lekt omkring" med några enklare exempel av satsen kom jag fram till ett något fungerande resonemang (är dock osäker kring huruvida det är korrekt). Här är en skiss, dock utan basfallet för $n = 1$ .

Induktionsantagande: $\displaystyle\sum_{k = 0}^{m}{m\choose k} a^{m - k}b^k = \left(a + b\right)^m$ för något positivt heltal $m$ .

Fallet för $n = m + 1$ blir då följande

$\displaystyle\sum_{k = 0}^{m + 1}{m + 1\choose k} a^{m + 1 - k}b^k = a^{m + 1} + b^{m + 1} + \sum_{k = 1}^{m}{m + 1\choose k} a^{m + 1 - k}b^k$ .

En omskrivning med Pascals identitet ger nu

$\displaystyle a^{m + 1} + b^{m + 1} + \sum_{k = 1}^{m}({m\choose k - 1} + {m\choose k})a^{m + 1 - k}b^k$

$\displaystyle= a^{m + 1} + b^{m + 1} + \sum_{k = 1}^{m}{m\choose k - 1}a^{m + 1 - k}b^k + \sum_{k = 1}^{m}{m\choose k}a^{m + 1 - k}b^k$ .

Låt $j = k - 1$ . Genom en substitution av $j$ i en av summorna erhålls

$\displaystyle a^{m + 1} + b^{m + 1} + \sum_{j = 0}^{m - 1}{m\choose j}a^{m - j}b^{j + 1} + \sum_{k = 1}^{m}{m\choose k}a^{m + 1 - k}b^k$

$\displaystyle= \left(a^{m + 1} + \sum_{k = 1}^{m}{m\choose k}a^{m + 1 - k}b^k\right) + \left(b^{m + 1} + \sum_{j = 0}^{m - 1}{m\choose j}a^{m - j}b^{j + 1}\right)$

$\displaystyle= a\left(\sum_{k = 0}^{m}{m\choose k}a^{m - k}b^k\right) + b\left(\sum_{j = 0}^{m}{m\choose j}a^{m - j}b^{j}\right)$ .

Induktionsantagandet ger nu att uttrycket ovan är lika med $a(a + b)^m + b(a + b)^m = (a + b)(a + b)^m = (a + b)^{m + 1}$ .

VSB?

Egenhändigt lånat från "nätet";

Svara

Visa senaste svar