Matematisk induktion

Från Wikipedia
(Omdirigerad från Induktionsbevis)
Hoppa till: navigering, sök
En informell beskrivning av matematisk induktion kan illustreras med fallande dominobrickor.

Matematisk induktion är en matematisk teknik för att bevisa påståenden som på något sätt har med de positiva heltalen att göra. Tekniken kan även tillämpas på de matematiska objekt som är vidareutvecklingar av de positiva heltalen, ordinaltalen.

Tekniken kan förstås med en analogi: Du har lika många dominobrickor som det finns positiva heltal och på varje dominobricka är skrivet ett positivt heltal. (Det finns inte två brickor på vilka samma heltal är skrivet.) Du ställer upp dominobrickorna på högkant i den ordning som talen på dem föreskriver, så att när en bricka välter så knuffar den till nästföljande bricka så att även den välter. Induktionsprincipen säger att samtliga dominobrickor kommer att bli välta, ifall den första brickan har blivit vält.

Matematisk beskrivning[redigera | redigera wikitext]

Formell beskrivning[redigera | redigera wikitext]

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.

Beskrivning med ord[redigera | redigera wikitext]

Låt A vara en mängd av positiva heltal som innehåller talet ett. Om A innehåller talet n+1 då det även innehåller talet n, så är A lika med mängden av alla positiva heltal.

Bevis[redigera | redigera wikitext]

Vanligtvis formuleras principen för matematisk induktion som ett axiom för de naturliga talen, se till exempel Peanos axiomsystem. Det är emellertid möjligt att inom vissa formella system härleda principen från andra antaganden, till exempel att mängden av naturliga tal är en välordnad mängd.

Vi skall använda en matematisk teknik som kallas motsägelsebevis. (Latin: Reductio ad absurdum.) Tekniken går ut på att anta att motsatsen till det vi vill bevisa är sann, och visa att detta leder fram till en motsägelse; ett påstående som aldrig kan vara sant.

Beteckna med symbolen A en mängd som innehåller talet 1 och som även innehåller talet n+1 om det innehåller det positiva heltalet n. Vi vill visa att mängden A är lika med mängden av alla positiva heltal.

Antag att A inte är lika med mängden av alla positiva heltal.

Då finns det positiva heltal som ligger utanför mängden A. Samla ihop dessa till en mängd som vi betecknar med symbolen B; detta är en icke-tom mängd bestående av positiva heltal. Enligt välordningsaxiomet för de positiva heltalen innehåller B ett minsta element, som vi betecknar med symbolen m.

Eftersom mängden A innehåller talet 1, kan elementet m inte vara talet 1; det är därför större än talet 1. Då är elementet m-1 ett positivt heltal som är mindre än talet m. Talet m-1 kan inte ligga i mängden B, eftersom m-1 då vore det minsta elementet i B. Därför måste talet m-1 ligga i mängden A. Men om elementet m-1 ligger i mängden A, så ligger det efterföljande talet (m-1) + 1 också i mängden A, det vill säga att talet m ligger i mängden A.

Vi har härmed visat att det finns ett element (m) som ligger både innanför- och utanför mängden A, vilket är en motsägelse.

Det var därför fel av oss att anta att mängden A inte var lika med mängden av positiva heltal.

Principen om matematisk induktion är därför bevisad.

Exempel på induktionsbevis[redigera | redigera wikitext]

Induktionsbevis är en viktig bevismetod inom matematiken. Typiskt används metoden för att bevisa att något är sant för alla naturliga tal. Man kan då beskriva metoden på följande sätt:

  • Kontrollera att påståendet är sant för ett tal n .
  • Antag att påståendet är sant för m>n, där m är ett godtyckligt naturligt tal.
  • Visa att påståndet då även gäller för m + 1.
  • Nu vet vi att påståndet är sant för n. Då är det även sant för varje tal större eller lika med n.

Aritmetisk talföljd[redigera | redigera wikitext]

Sats. Om n är ett positivt heltal så är summan

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

Bevis Visa först att satsen stämmer då n=1.

Om n=1 så är å ena sidan 1+2+3+\cdots+n = 1 och å andra sidan \frac{n(n+1)}{2} = \frac{1\cdot(1+1)}{2} = \frac{2}{2} = 1: Satsen verkar stämma då n=1.
Anta att satsen stämmer för det positiva heltalet n; detta steg i beviset kallas induktionsantagandet.
Det gäller att visa att satsen stämmer för nästa heltal, n+1: Visa att 1+2+3+\cdots+n+(n+1) = \frac{(n+1)(n+2)}{2}.
Genom att gruppera termerna i summan 1+2+3+\cdots+n+(n+1) på ett smart sätt kan man använda induktionsantagandet:
1+2+3+\cdots+n+(n+1) = (1+2+3+\cdots+n) + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)(1 + \frac{n}{2} ) = \frac{(n+1)(n+2)}{2}.
Resultat: Satsen stämmer för det positiva heltalet 1. Om satsen stämmer för det positiva heltalet n, så stämmer satsen för nästa positiva heltal, n+1. Enligt principen för matematisk induktion stämmer satsen för alla positiva heltal.

Vilket skulle bevisas.

Tal på formen 3^{2n+1}+5^{2n} är delbara med 4, men inte med 8[redigera | redigera wikitext]

Man kan också göra tvärtom för att visa att om ett påstående är falskt för n=p, så är det även falskt för n=p+1. Detta används i följande bevis.

  • Bevisa att för varje naturligt tal n är talet 3^{2n+1}+5^{2n} delbart med 4, men inte med 8.

Bevis: Förenkling ger k=3^{2n+1}+5^{2n}=3*3^{2n}+5^{2n}=3*9^n+25^n

För n=0 gäller alltså att k_0=3+1=4, och för n=1 fås att k_1=3*9+25=52. Både 4 och 52 är delbara med 4, men inte för 8. Nu har vi visat att det gäller för två basfall.

Antag nu att det är sant för n=p+1 (att det är delbart med 4), alltså k_{p+1}=27*9^p+25*25^p, då gäller för n=p+2:

k_{p+2}=27*9^{p+1}+25*25^{p+1}
k_{p+2}=27*9^{p+1}+25*25^{p+1}+216*9^p-216*9^p+600*25^p-600*25^p
k_{p+2}=(27*9^p+25*25^p)+216*9^p+600*25^p

Där parentesen motsvarar vårt antagande, som alltså skulle vara delbart med 4. 216 och 600 är båda delbara med 4, och således är även hela uttrycket delbart med 4. Induktionsprincipen ger att 3^{2n+1}+5^{2n} är delbart med 4 för alla naturliga tal n.

Om vi antar att k_{p+1} är delbart med 8, så visar det alltså sig att även k_{p+2} är delbart med 8, eftersom 216 och 600 är det. Problemet här är att vi inte kan påbörja induktionen eftersom vi inte har något basfall. Om vi däremot hade antagit att det var falskt för k_{p+1}, hade vi funnit med samma metod som ovan att det även är falskt för k_{p+2}. Då det är falskt för basfallen n=0 och n=1 (att det är delbart med 8), säger induktionsprincipen att 3^{2n+1}+5^{2n} inte är delbart med 8 för alla naturliga tal n, och det ursprungliga påståendet har bevisats.

Hur stort är talet n-fakultet?[redigera | redigera wikitext]

För att få en uppfattning om storleken hos talen n-fakultet (n!) skall vi visa att:

n! \leq n^n, \qquad n = 1,2,3,\dots \,.

För det första gäller olikheten då n = 1, eftersom 1! = 1. Vi antar att olikheten gäller för talet n=N och skall visa att den även gäller för nästa heltal, N+1.

(N+1)! = N! \, (N+1) \leq N^N \, (N+1) \leq (N+1)^N \, (N+1) = (N+1)^{N+1}.

Enligt principen för matematisk induktion gäller olikheten för alla positiva heltal: 1, 2, 3,\dots

Se även[redigera | redigera wikitext]

Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.