Övning 1: Bevisa med induktion att 1² + 2² + ... + n² = n(n+1)(2n+1)/6 för alla n≥1.

Basfall n=1: 1² = 1×2×3/6 = 1 ✓ Induktionssteg: Antag formeln gäller för n=k Visa för n=k+1: 1²+...+k²+(k+1)² = (k+1)(k+2)(2k+3)/6 Vänsterled = k(k+1)(2k+1)/6 + (k+1)² = (k+1)[k(2k+1)/6 + (k+1)] = (k+1)[k(2k+1)+6(k+1)]/6 = (k+1)(2k²+7k+6)/6 = (k+1)(k+2)(2k+3)/6 ✓ Svar: Sant enligt induktion

Övning 2: Bevisa att 7ⁿ - 1 är delbart med 6 för alla n≥1.

Basfall n=1: 7¹-1 = 6 = 6×1, så 6|6 ✓ Induktionssteg: Antag 6|(7ᵏ-1) för något k≥1 Visa 6|(7ᵏ⁺¹-1): 7ᵏ⁺¹-1 = 7×7ᵏ-1 = 7×7ᵏ-7+6 = 7(7ᵏ-1)+6 Första termen delbar med 6 (induktionshypotes och faktor 7) Andra termen delbar med 6 direkt Därför 6|(7ᵏ⁺¹-1) ✓ Svar: Sant enligt induktion

Medel

Matematisk induktion

Bevistekniker med matematisk induktion och stark induktion.

induktion basfall induktionssteg stark induktion bevis

Föreställ dig att du vill bevisa att alla dominobrickor i en lång rad kommer att falla om du knuffar den första. Du behöver två saker: att första brickan verkligen faller (basfall), och att om en bricka faller så faller även nästa (induktionssteg). Matematisk induktion fungerar på samma sätt - det är en kraftfull bevismetod för påståenden om naturliga tal.

Fördjupning

Matematisk induktion är en fundamental bevismetod för påståenden av formen 'för alla naturliga tal n ≥ n₀ gäller P(n)'. Metoden bygger på två komponenter: basfall som verifierar påståendet för det minsta värdet, och induktionssteg som visar att om påståendet gäller för n så gäller det även för n+1. Detta etablerar giltigheten för alla naturliga tal.

Principen för matematisk induktion

Matematisk induktion används för att bevisa påståenden P(n) som gäller för alla naturliga tal n ≥ n₀. Beviset består av två delar: basfall som visar P(n₀) är sant, och induktionssteg som visar att P(k) → P(k+1) för alla k ≥ n₀.

Induktionsprincipen: P(n₀) \land \forallk(P(k) \to P(k+1)) ⟹ \foralln\geqn₀ P(n)

Struktur av induktionsbevis

För att bevisa ∀n≥1 P(n):

1. Basfall: Visa P(1) är sant

2. Induktionssteg:

· Antag P(k) är sant för något k≥1 (induktionshypotes)

· Visa att P(k+1) också är sant

3. Slutsats: P(n) gäller för alla n≥1

Enkla induktionsbevis

De enklaste induktionsbevisen handlar om att bevisa formler för summor, produkter eller olikheter. Ett klassiskt exempel är summan av de första n naturliga talen. Nyckeln är att använda induktionshypotesen för att härleda nästa steg.

Formel att bevisa: 1 + 2 + ... + n = n(n+1)/2

Bevis för summan 1+2+...+n

Påstående: ∀n≥1, 1+2+...+n = n(n+1)/2

Basfall n=1: vänsterled = 1, högerled = 1(1+1)/2 = 1 ✓

Induktionssteg: Antag formeln gäller för n=k

Visa för n=k+1: 1+2+...+k+(k+1) = (k+1)(k+2)/2

Vänsterled = (1+2+...+k) + (k+1) = k(k+1)/2 + (k+1)

= (k+1)(k/2 + 1) = (k+1)(k+2)/2 = högerled ✓

Bevis för geometrisk summa

Påstående: ∀n≥0, 1+r+r²+...+rⁿ = (rⁿ⁺¹-1)/(r-1) för r≠1

Basfall n=0: 1 = (r¹-1)/(r-1) = 1 ✓

Induktionssteg: Antag sant för n=k

1+r+...+rᵏ+rᵏ⁺¹ = (rᵏ⁺¹-1)/(r-1) + rᵏ⁺¹

= (rᵏ⁺¹-1+rᵏ⁺¹(r-1))/(r-1) = (rᵏ⁺²-1)/(r-1) ✓

Induktion för delbarhet

Matematisk induktion är särskilt kraftfull för att bevisa delbarhetspåståenden. Dessa bevis kräver ofta algebraisk manipulation för att visa att uttrycket för n=k+1 innehåller uttrycket för n=k plus något som är delbart med den givna faktorn.

Bevis: n³-n är delbart med 3

Påstående: ∀n≥1, 3|(n³-n)

Basfall n=1: 1³-1 = 0 = 3×0, så 3|0 ✓

Induktionssteg: Antag 3|(k³-k) för något k≥1

Visa 3|((k+1)³-(k+1)):

(k+1)³-(k+1) = k³+3k²+3k+1-k-1 = k³-k+3k²+3k

= (k³-k) + 3(k²+k)

Första termen delbar med 3 (induktionshypotes)

Andra termen delbar med 3 (faktor 3)

Därför är hela uttrycket delbart med 3 ✓

Stark induktion

I stark induktion antar vi att påståendet gäller för alla värden från basfallet upp till k, inte bara för k. Detta ger oss mer kraft i induktionssteget och är nödvändigt för vissa bevis, särskilt de som involverar rekursiva definitioner.

Stark induktion: P(n₀) \land \forallk(P(n₀)\land...\landP(k) \to P(k+1)) ⟹ \foralln\geqn₀ P(n)

Bevis med stark induktion: Fibonacci-tal

Påstående: Varje Fibonacci-tal Fₙ ≤ 2ⁿ för n≥1

Fibonacci: F₁=1, F₂=1, Fₙ=Fₙ₋₁+Fₙ₋₂ för n≥3

Basfall: F₁=1≤2¹=2 ✓, F₂=1≤2²=4 ✓

Induktionssteg: Antag Fᵢ≤2ⁱ för alla 1≤i≤k (k≥2)

Visa Fₖ₊₁≤2ᵏ⁺¹:

Fₖ₊₁ = Fₖ + Fₖ₋₁ ≤ 2ᵏ + 2ᵏ⁻¹ = 2ᵏ⁻¹(2+1) = 3×2ᵏ⁻¹ < 4×2ᵏ⁻¹ = 2ᵏ⁺¹ ✓

Strukturell induktion

Strukturell induktion används för rekursivt definierade objekt som träd, listor eller formler. Istället för att inducera över naturliga tal, inducerar vi över strukturens komplexitet. Basfallet täcker de enklaste strukturerna, och induktionssteget visar hur egenskapen bevaras när strukturen byggs upp.

Induktion över binära träd

Påstående: Antal blad i binärt träd = antal inre noder + 1

Basfall: Träd med en nod (bara rot)

· Antal blad = 1, antal inre noder = 0

· 1 = 0 + 1 ✓

Induktionssteg: Antag sant för träd T₁ och T₂

· Nytt träd T med T₁ och T₂ som subträd

· Blad(T) = Blad(T₁) + Blad(T₂)

· Inre(T) = Inre(T₁) + Inre(T₂) + 1

· Blad(T) = (Inre(T₁)+1) + (Inre(T₂)+1) = Inre(T₁)+Inre(T₂)+2 = Inre(T)+1 ✓

Vanliga fallgropar

Induktionsbevis kan gå fel på flera sätt. Vanliga misstag inkluderar att inte använda induktionshypotesen i induktionssteget, att bevisa fel riktning, eller att missa basfall. Det är viktigt att vara mycket noggrann med varje steg.

Felaktigt 'bevis' att alla hästar har samma färg

Påstående: I varje grupp av n hästar har alla samma färg

Basfall n=1: Trivialt sant ✓

Induktionssteg: Antag sant för k hästar

För k+1 hästar: ta bort första hästen → k hästar med samma färg

Ta bort sista hästen → k hästar med samma färg

Därför har alla k+1 hästar samma färg ✗

FEL: För k=1 överlappar inte de två grupperna!

Vanliga misstag

❌ Glömma att använda induktionshypotesen

Induktionssteget måste explicit använda antagandet att P(k) är sant

Exempel: Att bara visa P(k+1) utan att använda P(k) är inte induktion

❌ Felaktigt basfall

Basfallet måste verkligen vara det minsta värdet där påståendet gäller

Exempel: Om påstående gäller för n≥3, måste basfall vara n=3, inte n=1

❌ Antag det som ska bevisas

Induktionshypotesen är antagandet P(k), inte slutsatsen P(k+1)

Exempel: Kan inte anta P(k+1) när man ska bevisa P(k+1)

Tillämpningar

Algoritmer

Induktion används för att bevisa korrekthet och komplexitet av rekursiva algoritmer

Exempel: Bevis att mergesort sorterar en array med n element i O(n log n) tid

Talteori

Många skaff inom talteori bevisas med induktion

Exempel: Fermats lilla sats, egenskaper hos primtal, delbarhetspåståenden

Diskret sannolikhet

Induktion används för att bevisa formler för väntevärden och varianser

Exempel: Bevis att väntevärdet av summan equals summan av väntevärden

Övningar

1 Medel

Bevisa med induktion att 1² + 2² + ... + n² = n(n+1)(2n+1)/6 för alla n≥1.

Tips

Använd induktionshypotesen när du beräknar summan för n=k+1

Visa facit

Basfall n=1: 1² = 1×2×3/6 = 1 ✓
Induktionssteg: Antag formeln gäller för n=k
Visa för n=k+1: 1²+...+k²+(k+1)² = (k+1)(k+2)(2k+3)/6
Vänsterled = k(k+1)(2k+1)/6 + (k+1)²
= (k+1)[k(2k+1)/6 + (k+1)] = (k+1)[k(2k+1)+6(k+1)]/6
= (k+1)(2k²+7k+6)/6 = (k+1)(k+2)(2k+3)/6 ✓

Svar: Sant enligt induktion

2 Medel

Bevisa att 7ⁿ - 1 är delbart med 6 för alla n≥1.

Tips

Använd att 7ᵏ⁺¹ = 7×7ᵏ och faktorisera

Visa facit

Basfall n=1: 7¹-1 = 6 = 6×1, så 6|6 ✓
Induktionssteg: Antag 6|(7ᵏ-1) för något k≥1
Visa 6|(7ᵏ⁺¹-1):
7ᵏ⁺¹-1 = 7×7ᵏ-1 = 7×7ᵏ-7+6 = 7(7ᵏ-1)+6
Första termen delbar med 6 (induktionshypotes och faktor 7)
Andra termen delbar med 6 direkt
Därför 6|(7ᵏ⁺¹-1) ✓

Svar: Sant enligt induktion

3 Svår

Bevisa med stark induktion att varje heltal n≥2 kan skrivas som produkt av primtal.

Tips

Använd att om n inte är primtal så n=ab där 2≤a,b<n

Visa facit

Basfall n=2: 2 är primtal, så 2 = 2 (produkt av ett primtal) ✓
Induktionssteg: Antag påståendet för alla 2≤i≤k
Visa för n=k+1:
Fall 1: k+1 är primtal → k+1 är produkt av ett primtal ✓
Fall 2: k+1 är sammansatt → k+1 = ab där 2≤a,b≤k
Enligt induktionshypotes: a och b är produkter av primtal
Därför k+1 = ab är också produkt av primtal ✓

Svar: Sant enligt stark induktion

Sammanfattning

Matematisk induktion är en fundamental bevismetod för påståenden om naturliga tal. Den består av basfall (verifiera för minsta värde) och induktionssteg (visa P(k)→P(k+1)). Stark induktion tillåter användning av alla tidigare fall i induktionshypotesen. Strukturell induktion används för rekursivt definierade objekt. Induktion är kraftfull för att bevisa formler, delbarhet och egenskaper hos algoritmer.