Bevismetoder: induktion¶

Induktion är hur du bevisar ett påstående för alla naturliga tal på en gång, utan att kontrollera dem ett i taget (vilket aldrig skulle ta slut). Det är mindre ett ämne än en teknik — men det examineras i egen rätt, nästan alltid som en uppgift i del C där, som vanligt, nedskrivningen är merparten av poängen.

Den mentala bilden. Induktion är dominobrickor. Om du visar (1) att den första brickan faller, och (2) att varje bricka välter nästa, då får du dra slutsatsen att alla faller — även om du aldrig rörde de flesta. De två stegen nedan är exakt de två löftena.

Strukturen¶

Matematisk induktion

För att bevisa att \(P(n)\) gäller för alla \(n \geq n_0\):

Basfall. Bevisa \(P(n_0)\) direkt. (Detta är den första brickan. \(n_0\) är oftast \(0\) eller \(1\) — använd det värde påståendet faktiskt börjar vid.)
Induktionssteg. Anta att \(P(k)\) gäller för något \(k \geq n_0\) — det antagandet är induktionsantagandet — och använd det för att bevisa \(P(k+1)\). (Detta är "varje bricka välter nästa".)

Tillsammans låter dessa dig dra slutsatsen \(P(n)\) för alla \(n \geq n_0\).

Den subtila punkt nybörjare misstror: i induktionssteget får du anta just det du försöker bevisa — men bara för \(k\), för att fastställa det för \(k+1\). Det är inte cirkulärt, eftersom basfallet förankrar kedjan och steget bara någonsin skjuter ett steg högre.

Stark induktion är en variant där du antar att \(P\) gäller för alla värden upp till \(k\) (inte bara \(k\) självt) när du bevisar \(P(k+1)\). Grip efter den när \(P(k+1)\) beror på mer än det omedelbart föregående fallet — t.ex. en följd definierad från de två föregående termerna.

Hur man skriver ner ett (det är här poängen finns)¶

Tentamen bedömer presentationen explicit, och induktion är där en slarvig nedskrivning syns mest. Ett bevis för full poäng gör fyra saker omöjliga att missa:

Ange påståendet \(P(n)\) precist, som en fristående utsaga om \(n\).
Gör basfallet, och etikettera det. Det är en rad; att hoppa över det är en genuin logisk lucka (dominobrickor som alla välter varandra men där ingen faktiskt börjar falla bevisar ingenting).
Ange induktionsantagandet explicit — skriv ut, i symboler, exakt vad du antar.
Markera stället där du använder det. Sätt ett "I.A." över likhetstecknet, eller säg "enligt induktionsantagandet". Detta är den enda rad som förvandlar din algebra till ett faktiskt induktionsbevis.

Det vanligaste sättet induktionsbevis misslyckas

Att bevisa \(P(k+1)\) från grunden utan att någonsin använda \(P(k)\). Om induktionsantagandet aldrig åberopas, så behövde påståendet antingen ingen induktion alls, eller — mycket mer troligt — så är argumentet i hemlighet cirkulärt och antog det som skulle bevisas. Lackmustest: peka på den exakta rad där antagandet kommer in. Kan du inte det är beviset trasigt.

Standardformen för delbarhet¶

Den vanligaste induktionen på tentamen är ett delbarhetspåstående, och de ger alla vika för samma drag: i induktionssteget, skriv om \((k+1)\)-uttrycket så att \(k\)-uttrycket inuti blottas, och substituera sedan antagandet. Se det hända:

Tentamen (maj 2024, uppgift 7): bevisa \(19 \mid 3^{3n-2} + 2^{3n+1}\)

Basfall (\(n = 1\)). Sätt in:

\[ 3^{3(1)-2} + 2^{3(1)+1} = 3^{1} + 2^{4} = 3 + 16 = 19, \]

som är delbart med \(19\). Första brickan nere. ✓

Induktionsantagande. Anta påståendet vid \(n = k\): \(19 \mid 3^{3k-2} + 2^{3k+1}\). Den mest användbara formen att skriva det i är som en kongruens — omordnad så att en term uttrycks via den andra:

\[ 2^{3k+1} \equiv -3^{3k-2} \pmod{19} \]

Induktionssteg. Titta på \(n = k+1\) och skala av de extra faktorerna så att \(k\)-uttrycket kommer upp till ytan (notera \(3^{3(k+1)-2} = 3^{3k-2}\cdot 3^3\) och \(2^{3(k+1)+1} = 2^{3k+1}\cdot 2^3\)):

\[ \begin{aligned} 3^{3(k+1)-2} + 2^{3(k+1)+1} &= 3^{3k-2} \cdot 3^3 + 2^{3k+1} \cdot 2^3 \\ &\stackrel{\text{I.A.}}{\equiv} 3^{3k-2} \cdot 3^3 - 3^{3k-2} \cdot 2^3 \pmod{19} &&\text{(ersatte } 2^{3k+1} \text{ med antagandet)}\\ &= 3^{3k-2}\,(27 - 8) \\ &= 3^{3k-2} \cdot 19 \\ &\equiv 0 \pmod{19}. \end{aligned} \]

Så \(19 \mid 3^{3(k+1)-2} + 2^{3(k+1)+1}\), påståendet vid \(k+1\). Genom induktion gäller det för varje positivt heltal \(n\). \(\square\)

Två överförbara knep:

Gör antagandet till en kongruens (\(2^{3k+1} \equiv -3^{3k-2}\)). "Delar" är svårt att substituera; en kongruens slinker rakt in i en algebrakedja.
Substitutionen kollapsar två termer till en gemensam faktor (\(3^{3k-2}\)), och den kvarvarande \((27 - 8) = 19\) avslutar det. Den "kollapsa till en gemensam faktor" är mekanismen du styr mot varje gång.

Andra standardmål¶

Extrauppgiftsbladen drillar fyra former. Alla fyra använder samma disciplin — blotta \(k\)-fallet, tillämpa antagandet, städa upp:

Delbarhet. t.ex. \(4 \mid 5^n - 1\) för \(n \geq 0\), eller \(3 \mid n^3 - n\) för \(n \geq 0\). Precis metoden ovan.
Summationsformler. Bryt av den sista termen: \(\sum_{i=1}^{k+1} a_i = \big(\sum_{i=1}^{k} a_i\big) + a_{k+1}\). Tillämpa antagandet på parentesen, och gör sedan algebran för att matcha målformeln vid \(k+1\).
Olikheter. t.ex. \(2^{n+1} > n + 2\) för \(n \geq 1\). Samma skelett, men du begränsar i stället för att substituera en likhet — och du måste hålla reda på olikhetens riktning i varje steg.
Binomialidentiteter. t.ex. \(\binom{2n}{n} = \frac{1 \cdot 3 \cdot 5 \cdots (2n-1)}{n!}2^n\). Ta kvoten av på varandra följande termer; induktionssteget blir en liten förkortning.

Långsamt genomräknat: \(4 \mid 5^n - 1\)

Basfall (\(n = 0\)). \(5^0 - 1 = 1 - 1 = 0\), och \(4 \mid 0\) (noll är delbart med allt). ✓

Antagande. Anta \(4 \mid 5^k - 1\), dvs. \(5^k \equiv 1 \pmod 4\).

Steg. Blotta \(5^k\) inuti \(5^{k+1}\), och substituera sedan:

\[ 5^{k+1} - 1 = 5 \cdot 5^k - 1 \stackrel{\text{I.A.}}{\equiv} 5 \cdot 1 - 1 = 4 \equiv 0 \pmod 4. \]

Så \(4 \mid 5^{k+1} - 1\), vilket fullbordar induktionen. Samma tre slag varje gång: blotta, substituera, kollapsa.