Hur gör man induktionsbevis?
I ett "svagt" induktionsskydd letar du i slutändan efter en koppling mellan P (k) och P (k + 1) för att bevisa att ditt förslag är sant.
Matematisk induktion är en metod för matematisk bevis baserad på förhållandet mellan villkorliga uttalanden. Låt oss till exempel börja med det villkorliga uttalandet: "Om det är söndag kommer jag att titta på fotboll." Du kan göra följande uttalande att: "Om jag tittar på fotboll kommer jag att beställa takeout." Du kan följa detta uttalande med en annan: "Om jag beställer takeout, kommer jag inte att laga mat." Av dessa kan du med giltighet dra slutsatsen att: "Om det är söndag kommer jag inte att laga mat " på grund av det logiska förhållandet mellan dessa villkorliga uttalanden. Om du kan bevisa att det första uttalandet i en kedja av implikationer är sant, och varje uttalande innebär nästa, följer det naturligtvis att det sista påståendet i kedjan också är sant.Detta är hur matematisk induktion fungerar, och stegen nedan kommer att illustrera hur man konstruerar en formell induktionssäker.
Metod 1 av 2: använda "svag" eller "vanlig" matematisk induktion
- 1Bedöm problemet. Låt oss säga att du ombeds att beräkna summan av de första "n" udda siffrorna, skrivna som [1 + 3 + 5 +... + (2n - 1)], genom induktion. (Den sista termen här härrör från det faktum att om du fördubblar ett tal och sedan subtraherar 1 från det värdet kommer det resulterande talet alltid att vara udda.) Först kanske du märker att summan av på varandra följande udda tal verkar följa ett mönster (t.ex. 1 + 3 = 4; 1 + 3 + 5 = 9; 1 + 3 + 5 + 7 = 16; 1 + 3 + 5 + 7 + 9 = 25). Summan verkar vara antalet udda nummer du lägger till i kvadrat, eller hur? Nu när vi har en uppfattning om det mönster som spelas här kan vi börja vårt bevis.
- 2Ange egenskapen som kommer att bevisas med induktion. I vårt exempel har vi märkt ett mönster relaterat till summan av de första "n" udda siffrorna. För att slutföra uppgiften som vi tilldelats (dvs beräkna summan av de första "n" udda siffrorna) kan vi faktiskt ta oss tid att skriva ut alla udda siffror, börja med 1 hela vägen till "n" och lägga till dom upp. Men det finns ett enklare sätt. Baserat på vad vi observerade om de första summeringarna vi gjorde kunde vi erbjuda den här egenskapen, som vi kommer att försöka bevisa via induktion:
- 1 + 3 +... + (2n - 1) = n ^ 2
- Vi kommer att hänvisa till den här egenskapen som P (n), eftersom "n" är variabeln vi använde ovan.
- Det vänstra tecknet på ekvationen representerar summan av de första "n" udda siffrorna, som börjar med 1.
- 3Förstå konceptet bakom matematisk induktion. Det är bra att tänka på induktion i termer av domino, vilket påminner om "kedjan av implikationer" som diskuterades i inledningen ovan. Tänk på varje värde av "n" i egenskapen ovan, P (n), som en enskild domino, ordnad i en rad. Om vi kan visa att P (1) - det första värdet i kedjan - är sant, betyder det att vi kan slå över den första dominoen. Vidare, om vi antar att någon domino kan väljas (dvs. P (n) gäller för något godtyckligt värde på "n") och med det antagandet att följande domino också kan slås över (dvs. P (n + 1) är också sant), det betyder att vi kan slå över alla domino med vår angivna egendom. Detta betyder att egenskapen är sann i alla fall och vi har uppnått vårt mål genom induktion.
- 4Bevisa att grundfallet för fastigheten är sant. "Basfallet" för en viss egenskap är något litet värde som används för att visa att det första uttalandet för fastigheten gäller. I det här fallet kommer vi att använda "1", eftersom det här är det första udda talet och lätt att arbeta med. Om egenskapen gäller för basfallet har vi visat att vi kan slå över den första dominoen och vi kan gå vidare till nästa steg.
- P (1): 1 = 1 ^ 2
- P (1): 1 = 1 (Det höll, vi är bra. Första domino ner.)
- 5Ange den induktiva hypotesen. Nästa steg för induktion innebär att man antar ett antagande. I vårt exempel antar vi att för något godtyckligt värde av "n" -låt oss säga "k" - att uttalandet är sant. Det vill säga, vi tror att vår fastighet kommer att hålla oavsett vilket värde som används för "n". Om detta inte var sant skulle vår egendom (dvs. vår lösning på det ursprungliga problemet med att beräkna summan av de första "n" udda siffrorna) inte ha mycket nytta. Även om vi inte har bevisat någonting ännu, är detta antagande viktigt och har följande form:
- P (k): 1 + 3 +... + (2k - 1) = k ^ 2
- Kom ihåg att vi antar att detta är sant framöver i beviset (dvs att vi kan slå över varje enskild domino i kedjan).
- 6Bevisa att den induktiva hypotesen gäller för nästa värde i kedjan. Med andra ord antar vi att P (k) är sant och med det antagandet försöker vi bevisa att P (k + 1) också är sant. Om vi kan göra det har vi bevisat att vår teori är giltig med hjälp av induktion, för om man slår ner en domino (förutsatt att P (k) är sant) slår nästa domino ner (med det antagandet är det också att bevisa P (k + 1) sant) kommer alla dominoer att falla och vår egendom kommer att bevisas giltig. Så låt oss prova det:
- P (k): 1 + 3 +... + (2k - 1) = k ^ 2 är sant.
- P (k + 1): 1 + 3 +... + (2k - 1) + (2 (k + 1) - 1) = (k + 1) ^ 2
- Den kursiverade delen ovan på vänster sida av ekvationen representerar tillägget av nästa udda numrerade term i sekvensen, k + 1. Om vi kan göra den vänstra sidan lika med den högra sidan har vi lyckades.
- Från vårt antagande vet vi att den icke-kursiverade delen ovan är lika med k ^ 2, så låt oss göra den ersättningen.
- P (k + 1): k ^ 2 + (2 (k + 1) - 1) = (k + 1) ^ 2
- P (k + 1): k ^ 2 + 2k + 1 = (k + 1) ^ 2
- P (k + 1): (k + 1) ^ 2 = (k + 1) ^ 2
- 7Slutsatsen att egenskapen bevisas giltigt genom matematisk induktion. Genom att använda lite algebra har vi bevisat att vår egendom inte bara gäller för något godtyckligt värde på "n" utan också för värdet som följer det värdet. Vi har visat att P (1) är sant, antagit att P (k) är sant och bevisat att, baserat på det antagandet, är P (k + 1) också sant. För att använda vår fortsatta domino-analogi slog vi framgångsrikt den första dominoen och visade att vår fastighet har något värde. Sedan, förutsatt att någon godtycklig domino i kedjan kunde slås över, bevisade vi att detta nödvändigtvis kommer att slå ner nästa domino, oändligt ner resten av kedjan. Således har vi visat att vår egendom håller i allmänhet och har framgångsrikt avslutat vårt bevis med matematisk induktion.
Som tidigare är det första steget i alla induktionsbevis att bevisa att basfallet är sant.
Metod 2 av 2: användning av "stark" eller "komplett" matematisk induktion
- 1Förstå skillnaden mellan de två formerna av induktion. Ovanstående exempel är så kallad "svag" induktion, benämnd så inte på grund av en skillnad i kvalitet mellan de två induktionsmetoderna utan snarare för att illustrera en skillnad mellan vad som antas i den induktiva hypotesen för varje typ av bevis. De två bevisteknikerna är faktiskt ekvivalenta, det är bara ibland nödvändigt att anta mer i den induktiva hypotesen för att bevisa förslaget till hands. För att återvända till vår domino-analogi är det ibland inte tillräckligt att tro att P (k) är sant för att slå ner den domino som representeras av P (k + 1). Ibland måste du kunna slå ner alla dominoerna innan den för att bevisa att ditt förslag håller.
- 2Ange förslaget som ska bevisas med stark induktion. För att illustrera detta, låt oss överväga ett annat exempel. Låt oss säga att du ombeds att bevisa sant förslaget att alla heltal större än 1 kan skrivas som produkten av primtal.
- Som tidigare kommer vi att hänvisa till detta förslag som P (n), där "n" är det tal som kan uttryckas som en produkt av primtal.
- Eftersom vi talar om alla heltal större än 1 måste "n" vara större än eller lika med 2.
- Kom ihåg att ett primtal är ett positivt heltal större än 1 som bara kan delas, utan en rest, av sig själv och 1.
- 3Bevisa att basfallet är sant. Som tidigare är det första steget i alla induktionsbevis att bevisa att basfallet är sant. I det här fallet kommer vi att använda 2. Eftersom 2 är ett primtal (endast delbart av sig själv och 1) kan vi dra slutsatsen att basfallet är sant.
- 4Ange den (starka) induktiva hypotesen. Här är skillnaden mellan "svag" och "stark" induktion tydligast, eftersom detta steg är den enda skillnaden mellan de två formerna av induktivt bevis. Den induktiva hypotesen för "svag" induktion skulle anta att för något godtyckligt värde på "n" - igen, låt oss använda "k" - som propositionen innehåller. Vi skulle sedan använda detta antagande för att bevisa att nästa värde i kedjan är sant, så att vi kan avsluta vårt förslag är övergripande giltigt. För detta påstående antar vi dock att P (k) är sant, inget om P (k + 1). Denna typ av "svagt" antagande är otillräckligt här, så vi måste anta mer. Den induktiva hypotesen för "stark" induktion, i stället för att helt enkelt anta att P (k) är sant, antar att för alla värden på "n"mellan basfallet och "k", att förslaget är sant. Vi kommer att använda detta förhållandevis starkare antagande (dvs. vi antar mer) för att bevisa förslaget sant.
- Denna typ av "starkt" antagande är det som skiljer de två bevisformerna.
- I det här fallet antar vi att, för något värde av k ≥ 2, att varje heltal "n" så att 2 ≤ n ≤ k kan skrivas som produkten av primtal.
- 5Bevisa att den "starka" induktiva hypotesen gäller för nästa värde i kedjan. Vi kommer nu att använda detta starka antagande för att bevisa att P (k + 1) också gäller, och därigenom bevisa giltigheten av vårt förslag totalt. Det finns två relevanta resultat för "k + 1." Om "k + 1" är ett primtal, håller vårt förslag och vi är klara. Om "k + 1" inte är ett primtal kommer det att ha en minsta primfaktor, som vi kommer att beteckna som "p." Därför kan "k + 1" uttryckas som produkten av "p" och något annat tal, "x." Eftersom "x" nödvändigtvis kommer att vara mindre än "k", säger vår induktiva hypotes oss att "x" kan skrivas som en produkt av primtal, vilket i slutändan betyder att - oavsett om "k + 1" är primt eller inte, kan det skrivas som en produkt av primtal.
- 6Avsluta förslaget är giltigt bevisat av stark matematisk induktion. Med hjälp av vår "starka" induktiva hypotes kunde vi bevisa vårt förslag som hölls när "svag" induktion skulle ha varit otillräcklig för att göra det. Försök med "svag" induktion först, för det faktum att du antar mindre teoretiskt gör logiken bakom beviset starkare, i motsats till namngivningskonventionerna som används för dessa två typer av bevis. Matematiskt är de två induktionsformerna dock ekvivalenta.
Så här fungerar matematisk induktion, och stegen nedan illustrerar hur man konstruerar ett formellt induktionsskydd.
- I ett "svagt" induktionsskydd letar du i slutändan efter en koppling mellan P (k) och P (k + 1) för att bevisa att ditt förslag är sant. I ett "starkt" induktionsskydd letar du efter en koppling mellan P (vilket värde som helst "n" mellan baslådan och "k") och P (k + 1).
- Om "stark" induktion håller, så gör regelbunden induktion, och vice versa. Kom ihåg att dessa två typer av bevis är likvärdiga och att den ena inte är bättre än den andra. "Stark" induktion ger ibland lite hjälp att skriva ut beviset när den induktiva hypotesen för "svag" induktion inte tydligt bevisar förslaget till hands.
- Induktion fungerar på grund av välordningsprincipen. Det vill säga varje uppsättning positiva heltal har ett minsta element. I vårt exempel var det minsta elementet 1.
- Induktion används normalt för att bevisa att en egenskap är sant för alla naturliga tal. Det betyder att du kommer att arbeta med positiva heltal (icke-bråkdelar, eller heltal).
I ett "starkt" induktionsskydd letar du efter en koppling mellan P (vilket värde som helst "n" mellan baslådan och "k") och P (k + 1).
- Glöm inte basfallet! Det är ofta lätt att förbise detta enkla steg, eftersom det är ganska trivialt. Ditt induktiva bevis kommer dock att vara ofullständigt utan det.
- Blanda inte matematisk induktion med begreppet induktivt resonemang, där man försöker nå en sannolik slutsats baserat på observerade bevis. Matematisk induktion är faktiskt deduktivt resonemang som använder logik för att flytta från vissa, tydliga förutsättningar till en bestämd slutsats.
Kommentarer (1)
- Otrolig. Förklarade mycket bättre än någon lärare, handledare eller professor jag någonsin har haft. Tack till den som skrev detta.
