Komplicerad matematisk induktion

God afton. Vad som räknas som komplicerad matematisk induktion är förstås väldigt individuellt. Vi räknar med att du tidigare kanske klarat några induktionsuppgifter, men när det är mycket så kommer du inte hela vägen fram. Om du däremot är professor i matematik bör kommande vara en tämligen enkel sak.

Ett svårt påstående att bevisa med induktion

Vi vill visa att nedanstående är sant för alla positiva heltal.

1^2-2^2+3^2-4^2 + \dots + (-1)^{n-1}n^2 = (-1)^{n+1}\cdot\frac{n(n+1)}{2}

Är påståendet sant för n=1?

Vi sätter upp vänsterled och högerled,

VL=(-1)^{1-1}1^2=(-1)^0\cdot1^2 = 1

samt vårt högerled

HL=(-1)^{1+1}\frac{1(1+1)}{2} = (-1)^2\cdot\frac{2}{2}=1

Detta är sant, alltså

VL=HL

Vi kan nu gå vidare i vår bevisning.

Antag att det är sant för n=k

Nu gör vi vårt induktionsantagande, det vill säga att påståendet är sant för vilket tal som helst.

1^2-2^2+3^2-4^2 + \dots + (-1)^{k-1}k^2 = (-1)^{k+1}\cdot\frac{k(k+1)}{2}

Visa att det gäller för n=k+1

1^2-2^2+3^2-4^2 + \dots + (-1)^{k-1}k^2+ (-1)^{(k+1)-1}\cdot(k+1)^2 = (-1)^{(k+1)+1}\cdot\frac{(k+1)((k+1)+1)}{2}

Vi kan substituera in vårt induktionsantagande direkt och sedan snygga upp det något.

(-1)^{k+1}\cdot\frac{k(k+1)}{2} + (-1)^{(k+1)-1}(k+1)^2 = (-1)^{(k+1)+1}\cdot\frac{(k+1)((k+1)+1)}{2}

Om vi adderar ihop termer och parenteser får vi något mer lättjobbat.

(-1)^{k+1}\cdot\frac{k(k+1)}{2} + (-1)^{k}(k+1)^2 = (-1)^{(k+2)}\cdot\frac{(k+1)(k+2)}{2}

På högerledet har vi följande faktor,

(-1)^{k+2}=(-1)^k\cdot(-1)^2=(-1)^k

Då skriver vi vårt nya påstående på följande vis, det kanske inte är världens största steg, men det gör det lite enklare.

(-1)^{k+1}\cdot\frac{k(k+1)}{2} + (-1)^{k}(k+1)^2 = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

I vänsterledet finns följande faktor,

(-1)^{k+1}=(-1)^k\cdot(-1)^1 = -(-1)^k

Vi skriver om det hela som

-(-1)^{k}\cdot\frac{k(k+1)}{2} + (-1)^{k}(k+1)^2 = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

Bryt ut (-1)^{k} i vänsterledet,

(-1)^{k}\Big(-\frac{k(k+1)}{2} + (k+1)^2 \Big) = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

Byt plats på termerna inuti parentesen i vänsterledet

(-1)^{k}\Big((k+1)^2 -\frac{k(k+1)}{2}\Big) = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

Förläng och skriv på samma bråksträck, ungefär här börjar vi verkligen se att vårt induktionsbevis kommer fungera!

(-1)^{k}\Big(\frac{2(k+1)^2 - k(k+1)}{2}\Big) = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

Faktorisera ut (k+1).

(-1)^{k}\Big(\frac{(k+1)\big(2(k+1) - k\big)}{2}\Big) = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

Expanderar vi sista parentesen i vänsterledet och adderar ihop termerna finner vi att beviset är sant. Uttrycken skiljer såg åt på ett multiplikationstecken, men det är endast där för att det ska bli tydligare och förändrar ingenting.

(-1)^{k}\Big(\frac{(k+1)(k+2)}{2}\Big) = (-1)^{k}\cdot\frac{(k+1)(k+2)}{2}

Påståendet är alltså sant enligt matematisk induktion.

Notering

Det är väldigt sällan såhär många små steg skrivs ut, det är inget fel att skriva ut många steg men det kan ta längre tid. När du gör ditt bevis skriver du precis så många steg du tycker behövs, eller så många steg som du vet att din lärare tycker du behöver skriva ut för att få full pott på provet.