Induktionsbevis för talföljder

God kväll! Idag ska vi titta på matematisk induktion. En del inom matematiken som många tycker är extremt jobbig och arbetsam, och det är förvisso sant innan det går med automatik. Idag börjar vi lätt och ledigt med några exempel för att i senare genomgångar visa induktion med summatecken och induktion tillsammans med deriveringsregler.

Vad är matematisk induktion?

Induktion är ett sätt att bevisa ett påstående om egenskaper för talföljder. Det går kortfattat ut på att bevisa att egenskapen är sann för det första fallet. Sedan antas det vara sant för ett speciellt tal, och då ska det vara sant för det speciella talet, adderat med 1.

1+2+3+4+5…+n

Vårt första exempel är en tydlig uppgift på hur induktion kan används för att bevisa något. Någon påstår att följande är sant då n är ett heltal:

1+2+3+\dots + n =\frac{ n(n+1) }{ 2 }

Steg 1 – Kontrollera om det är sant för n = 1

Det första vi gör i induktion är att kontrollera om det är sant för det första fallet, det vill säga när n=1. Detta kan vi göra genom att dela upp ovanstående i två delar, VänsterLed och HögerLed.

  • VL = 1 + 2 + 3 + \dots n
  • HL = \frac{n(n+1)}{2}

n=1 erhåller vi följande:

  • VL = 1
  • HL = \frac{1+1}{2}=\frac{2}{2}=1

Av detta ser vi att VL=HL. Vi kan nu gå vidare till nästa steg i induktionsbeviset.

Steg 2 – Antag att det är sant för n=k

I steg nummer 2 antager vi att sambandet är sant för n=k. Det vill säga, vi antager helt enkelt att det vi vill bevisa är sant för vilket heltal som helst. Detta är vårt induktionsantagande.

1+2+3+\dots + k =\frac{ k(k+1) }{ 2 }

Vi vänder på den en gång för att göra det tydligare vad vi gör senare. Detta steg är enbart förtydligande och inget som påverkar själva beviset.

\frac{ k(k+1) }{ 2 } = 1+2+3+\dots + k

Steg 3 – Visa att det är sant för n = k + 1

Nu kommer det som kan bli lite rörigt. Nu ska vi bevisa att det är sant för heltalet precis efter k. Det vi gör nu är att byta ut n mot k +1 på alla ställen n står. I vänsterledet är k +1 självklart talet som kommer precis efter k. Följande ska vi alltså bevisa är sant:

1+2+3+\dots + k + (k +1) =\frac{ (k+1)((k+1)+1) }{ 2 }

Genom att använda vårt induktionsantagande i steg 2 skrivs detta om som, se till att du verkligen förstår vad nedanstående steg kommer ifrån, annars kommer alla induktionsbevis bli mycket svårare än de egentligen är.

\frac{ k(k+1) }{ 2 } + (k +1) =\frac{ (k+1)((k+1)+1) }{ 2 }

Vi vill bryta loss en faktor, och för tydlighetens skull kan ovanstående skrivas om till:

\frac{k}{ 2 }(k+1) + (k +1) =\frac{ (k+1)((k+1)+1) }{ 2 }

Genom att faktorisera k+1 i vänsterledet kan vi skriva det som följande:

(k +1)(\frac{k}{2}+1) =\frac{ (k+1)((k+1)+1) }{ 2 }

Sedan sätter vi andra faktorn i vänsterledet under gemensam nämnare.

(k +1)(\frac{k}{2}+\frac{2}{2}) =\frac{ (k+1)((k+1)+1) }{ 2 }

Sätt på samma bråksträck i andra faktorn i vänsterledet.

(k +1)(\frac{k+2}{2}) =\frac{ (k+1)((k+1)+1) }{ 2 }

Nu är vi såpass nära att vi skulle kunna sluta om vi ville, men vi fortsätter för att göra det extra tydligt. Bryt ut nämnaren ur andra faktorn i vänsterledet och sätt den under hela produkten:

\frac{(k +1)(k+2)}{2} =\frac{ (k+1)((k+1)+1) }{ 2 }

Sista steget innan de är identiska:

\frac{(k +1)((k+1)+1)}{2} =\frac{ (k+1)((k+1)+1) }{ 2 }

Avsluta med att skriva något i följande stil, påståendet är alltså sant enligt matematisk induktion.

Fin matematisk definition av induktion

Det vi inledde genomgången med kan skrivas som:

  • P(n_0) är sant där n_0 \in\mathbb{R}
  • P(k) \Rightarrow P(k+1)~~~\forall k\in \mathbb{N}

Det är i text samma sak som:

  • Första utfallet är sant
  • Om det är sant för ett utfall beroende på k, så är utfallet sant även för k +1, där k är ett heltal

Om du inte förstår något av ovanstående, ta det lugnt och gör några av nedanstående exempel. En del lär sig aldrig hur induktion fungerar, men lär sig lösa alla på samma sätt men med utbytta siffror.