Citat:
Ursprungligen postat av
DenSvartaBollen
Tack, som sagt var , jag vill gärna öva på induktionsbevis.... jag har svårt fär det.
Det är som transkript säger; vi antar att någonting gäller för k och det vi sen visar är att det då också måste gälla samma sak för k+1. Om k termer beskrivs av f(k) så vill vi alltså visa att k+1 termer beskrivs av f(k+1).
Ungefär som jag gjorde här, vi antar att k objekt kan permuteras på k! sätt, sen visar vi på något vis att om det gäller så kan (k+1) objekt permuteras på (k+1)! sätt. Givet antagandet "k objekt ⇒ k! permutationer" så följer onekligen "k+1 objekt ⇒ (k+1)! permutationer."
Lite enklare exempel:
Vi vill visa att (-n)² ≥ 0. Om n < 0 så är det ganska givet, eftersom vi får positiv term innanför parentesen. Så vi antar att n ≥ 0.
Visa att det gäller för n = 0: (-0)² = 0 ≥ 0. Check.
Antag att det gäller för n = k; då har vi att (-k)² ≥ 0.
Visa att det, givet antagandet, gäller att (-(k + 1))² ≥ 0. Vi börjar med att utveckla uttrycket:
(-(k + 1))² =
-(k + 1) ∙ -(k + 1) = { multiplicera in -1 i båda parenteserna }
(-k - 1) ∙ (-k - 1) =
(-k)(-k) + (-1)(-k) + (-1)(-k) + (-1)(-1) =
(-k)² + 2k + 1.
Nu använder vi antagandet. (-k)² ≥ 0. Vi har även att k ≥ 0. +1 > 0 också. Så vi har bara termer som är större än eller lika med 0, alltså är summan av alla termerna också större än eller lika med 0.
Det var precis det vi ville visa, så beviset är klart. Notera att det som gör att det fungerar är att vi kan använda vårt induktionsantagande för (-k)²; antagandet leder direkt till att beviset funkar. Alltså har vi visat att givet antagandet för (-k)² ≥ 0 så följer (-(k + 1))² ≥ 0.
Notera att det finns ett basfall som vi visade först av allt, nämligen k = 0. På grund av vårt bevis gäller det även för k=1, och då gäller det även för k=2, osv. Tack vare induktions
axiomet så gäller det för alla k ∈ ℕ.