Är det ett godkänt induktionsbevis?
Hej,
Jag har en fråga angående induktionsbevis. Om man börjar med ett påstående P(n) och antar det gäller för något n = k. Om man börjar med P(k) i induktionssteget och landar i P(k-1), är induktionsbeviset då godkänt?
Tack.
Undersök istället P(k+1) i induktionssteget. Med samma logik som du använt borde det då utmynna i P(k). Om jag förstår dig rätt har du då att:
- Påståendet P(k) stämmer för något k
- Påståendet P(k+1) stämmer om P(k) stämmer
Och då har du visat att P(n) stämmer för alla .
Skaft skrev:Undersök istället P(k+1) i induktionssteget. Med samma logik som du använt borde det då utmynna i P(k). Om jag förstår dig rätt har du då att:
- Påståendet P(k) stämmer för något k
- Påståendet P(k+1) stämmer om P(k) stämmer
Och då har du visat att P(n) stämmer för alla .
Okej, så det är alltså okej att göra på detta vis, att gå från k+1 till k, eftersom vi antagit att P(k) stämmer, så stämmer även k + 1, och på så vis för alla n större eller lika med k. Stämmer mitt resonemang?
Ja, beroende på vad du menar med "gå från k+1 till k" =) Man kan ju inte bara byta den ena mot den andra. Man måste visa att fallet k+1 hänger ihop med fallet k, så att man kan dra slutsatsen "om fallet k gäller, då gäller även fallet k+1". Då behöver man sen bara visa fallet k, så får man hela kedjeeffekten som induktionsbevis bygger på. Men det var nog vad du menade, det låter som du fattat.
Om man kan sluta sig till p(k) om man vet att p(k+1) är sant, men inte det omvända, så fungerar det inte. Men jag kanske missförstår frågan.
Skaft skrev:Ja, beroende på vad du menar med "gå från k+1 till k" =) Man kan ju inte bara byta den ena mot den andra. Man måste visa att fallet k+1 hänger ihop med fallet k, så att man kan dra slutsatsen "om fallet k gäller, då gäller även fallet k+1". Då behöver man sen bara visa fallet k, så får man hela kedjeeffekten som induktionsbevis bygger på. Men det var nog vad du menade, det låter som du fattat.
Ja, det var så jag menade. Exempelvis om jag börjar såhär
P(k+1) är något påstående för en olikhet som vi skall bevisa är sann, och så utvecklar jag och förenklar och landar sedan på P(k) istället för P(k+2), då är frågan ifall det är ett rätt induktionsbevis, förutsatt att P(k) är antaget till att vara sann? Hoppas det var så du också menade.
Det låter som att det stämmer. Du får förstås gärna visa det bevis som du känner dig osäker på =)
