Induktion (matematisk sådan)


Från Wikipedia: Låt P(n) vara ett påstående som har att göra med ett positivt heltal n, och antag att följande påståenden är sanna:

  • P(1) är sant.
  • \forall p \in \mathbb{N}:P(p) \Rightarrow P(p+1).

Då är påståendet P(n) sant för varje val av det positiva heltalet n.

Lätt som en plätt, eller?

Alla tycker induktion är svårt

Alla som någonsin har varit lärare i grundläggande matematikkurser på universitet har stött på svårigheter inom ett specifikt avsnitt: induktion. Det har skrivits många kompendieinlägg och artiklar i ämnet, det går att hitta massvis med förklaringar och exempel, men ändå har så många så svårt för det. Varje år är det kanske 30 elever man har och 29 av dem har svårigheter med induktion.

Nyligen fick jag ett mail som bad om hjälp med en induktionsuppgift. Problemet för personen var att det inte var en standarduppgift (som handlar om summor, vänsterled=högerled, etc.), och fattar man inte induktionsprincipen då, så är man fast.

Vad induktion inte är

För att börja kasta lite ljus över ämnet, kan jag berätta om vad induktion inte är.

1. Det är inte en metod. Det påminner om en metod väldigt mycket, “stoppa in basvärden här”, “skriv induktionsantagandet där”, “härled induktionssteget mha induktionsantagandet”. Jag tror det är det som förklaringen av induktionsprincipen faller på. Den förklaras  mycket formellt, precis som en metod, och därför också uppfattas som sådan. Finns alltså inget sätt att lösa allmännt induktionsproblem!

2. Det är absolut inte en formel. Om man bara har sett summationsuppgifter, säg “Visa att summan av de första n positiva heltalen är n(n+1)/2” och liknande, tror man kanske att induktionspincipen är en slags formel. Man stoppar in lite summor här och var och blir det likhet, så är man klar. Så är det på sätt och vis med summationsuppgifter, dock faller inte alla de ut lika lätt som exemplet jag tog upp.

3. Det är inte en sats, en teori, en bok, en tupp osv.

Var är det då? Induktionen är en princip, ett axiom och så önskas. Det betyder att det är någonting som vi människor (matematiskt lagda) tycker borde gälla. Det är någonting som följer logikens lagar. Till exempel “äpplet faller inte långt från trädet” är ett av naturens lagar och det är lite konstigt att titta på det som en metod för beräkning av äpplenas banor. Ett mer matematiskt exempel är “Om det finns en linje i planet och en punkt utanför linjen, så kan man bara rita en linje genom punkten som är parallell med den första, ändrar man något så kommer första linjen korsas”. Det är ju ganska naturligt att det är så, men det är fortfarande varken metod eller formel.

Hur jag lärde mig induktion

Det skedde relativt tidigt, då jag ännu inte fattade mig på summationstecknet, vilket nog hjälpte för att förstår principen bra (kanske det som är lösningen, lära ut summa efter att man lär ut induktion på grundläggande algebra-kursen?). Jag fick några problem på fritiden, så jag försökte klura ut hur man löste dem. Men det är väldigt svårt att komma på principen själv, så jag lyckades inte först. Sen när man förstår principen så säger det “klick” och sådana problem löses på bara några minuter.

Och hur förstår man principen då? Jo, genom exempel! Exempel från matten eller vardagen spelar ingen roll. Vitsen är att när någon berättar att man visar någonting att börja med (bas) och sedan visar att “varje leder till nästa” (induktionssteg), så är det klart att det följer för alla. “Självklart måste det vara så!”, säger man då, och då har man förstått. Nästa svåra steget är att översätta lösningar till matematikspråket. Just “översätta”, eftersom mitt största råd är att lösa varje uppgift med ord först, så gott det går, och bara sedan försöka formalisera. Till att börja med: glöm bort vad induktion är och försök lösa de här, så återkommer jag med utförliga exempellösningar.

6 reaktioner till “Induktion (matematisk sådan)”

  1. Det kan vara intressant att poängtera att induktionsaxiomet just är ett axiom för positiva tal, så egentligen så är den en av ingredienserna som talar om vad ett naturligt tal är snarare än något som talar om vad som kan bevisas (tillsammans med andra saker som att det exempelvis existerar ett naturligt tal 1 odyl). Det går utmärkt att hitta saker som beter sig som naturliga tal i övrigt men som inte har med det axiomet, exempelvis positiva reella tal.

    Det induktionsaxiomet “egentligen” säger kan ses som att man kan komma åt varje naturligt tal genom att starta i 1 och ta ett steg i taget framåt. Med en liten omformulering så säger axiomet att om vi har en mängd M sådan att den innehåller det naturliga talet 1 och att vi för varje naturligt tal som ingår i M har att det påföljande talet n+1 ingår i M så gäller det att alla naturliga tal ligger i M.
    Sedan så kan vi låta M bestå av alla naturliga tal för vilket ett påstående X gäller om vi vill ha tillbaka den ursprungliga formuleringen.

    Axiom behöver inte vara något som är “självklart”. Ofta så kan man med olika axiom få olika matematiska teorier. Valentinas exempel “Om det finns en linje i planet och en punkt utanför linjen, så kan man bara rita en linje genom punkten som är parallell med den första, ändrar man något så kommer första linjen korsas” är ett bra sådant, det går mycket bra att konstruera andra geometrier genom att ändra detta axiom. Om man exempelvis ritar saker på en sfär så kommer varje par av linjer (som på sfären är storcirklar som exemplevis ekvatorn) att korsa varandra två ggr. Så från den sfäriska synvinkeln så borde det axiomet snarare vara “Om det finns en linje i planet och en punkt utanför linjen, så kommer varje linje genom punkten att korsa den första linjen två och endast två gånger”.

    Om vi återgår till induktion så tycker jag den kanske mest intuitiva förklaringen är att se det som en rad dominobrickor. Om en bricka faller så faller nästa bricka motsvarar att om det gäller för p så gäller det för p+1. Att sedan verkligen knuffa den första brickan är då att visa att det gäller för p=1. Då vi knuffat på den första brickan så faller sedan alla brickorna omkull efter varandra.

  2. Tack för förklaringarna, Johan!

    Dominoförklaringen är förstås min favorit, frågan är om det går att hitta fler sådana intuitiva exempel. Jag tänkte i nästa inlägg förmedla känslan med hjälp av exempel, sådana som skiljer sig från standardproblem så mycket som möjligt. Ska också ta upp ett exempel där “induktionsresonemanget” går fel.

    Ja, axiom är ofta “självklara” givet vilken värld vi lever i. Själv lever jag tydligen på en platt planet :)

  3. Hejsan!
    Vart någonstans finns dina lösnings förslag. Hittade nyss in på denna blogg och ville kolla in dem ;)

    Mvh

  4. Hej dili!

    Jag kan inte heller hitta lösningsförslagen, så jag gissar att mitt gamla lovade mer än vad hon kunde hålla! Jag skrev nämligen bara en utförlig lösning, på uppgift 3, som du hittar på den här länken: http://mattebloggen.com/2009/02/kvadratuppdelning/

    Vilken lösning är du just nu mest intresserad av? Det får bli mattebloggens nästa gåta (med lösning).

Kommentera