Diskret matte- induktionsbevis
Hej, kan någon av er kolla snabbt om jag har tänkt korrekt.
uppfiten frågan:
Låt P(n) beteckna något matematisk påstående om talet n. (Några exempel på matema-
tiska påståenden om talet n är påståendena ”n(n + 2) är ett jämnt tal” och ”2n > n”.
Låt oss nu säga, för det första, att du på något sätt vet att P(1) verkligen är ett sant
påstående. (Det är till exempel inte sant för det första exemplet ovan: 1 ·(1 + 2) = 3 är ju
inte ett jämnt tal, men det är sant för det andra exemplet, ty 2 ·1 = 2 > 1.) Låt oss, för
det andra, säga att du också på något sätt vet att om påståendet P(p) skulle vara sant
för något visst värde på p så måste även påståendet P(p+1) vara sant. Förklara nu för en
skeptisk person varför du då också vet att även P(10) är ett sant påstående, och i själva
verket att P(n) är sant för varje n ≥1.
Din förklaring bör börja så här: ”Vi vet redan att P(1) är sant. Vi vet då också, genom att
sätta in p = 1 i det andra antagandet, att P(2) är sant. Vi vet då också, genom att sätta
in in p = 2 i det andra antagandet, att P(3) är sant.” Komplettera denna förklaring upp
till P(10). Förklara sedan att samma sorts förklaringskedja går att skriva upp för varje
n ≥1.
Svaren: Vi vet redan att P(1) är sant. Vi vet då också, genom att sätta p = 1 i det andra antagandet, att P(2) är sant. Vi vet då också, genom att sätta in p = 2 i det andra antagandet, att P(3) är sant. Vi vet då också, genom att sätta in p = 3 i det andra antagandet, att P(4) är sant. Vi vet då också, genom att sätta in p = 4 i det andra antagandet, att P(5) är sant. Vi vet då också, genom att sätta in p = 5 i det andra antagandet, att P(6) är sant. Vi vet då också, genom att sätta in p = 6 i det andra antagandet, att P(7) är sant. Vi vet då också, genom att sätta in p = 7 i det andra antagandet, att P(8) är sant. Vi vet då också, genom att sätta in p = 8 i det andra antagandet, att P(9) är sant. Vi vet då också, genom att sätta in p = 9 i det andra antagandet, att P(10) är sant. Således kan vi se att om P(n) är sant för ett givet värde på n, så är det också sant för nästa värde på n. Därför, eftersom P(1) är sant, kan vi dra slutsatsen att P(n) är sant för varje n ≥1
”Således kan vi se att om P(n) är sant för ett givet värde på n, så är det också sant för nästa värde på n. Därför, eftersom P(1) är sant, kan vi dra slutsatsen att P(n) är sant för varje n ≥1”
Egentligen vet jag inte om det hjälper att gå upp till 10 eller hundra eller tusen. Du kanske övertygar en skeptisk person, men påståendet blir inte säkrare för att du demonstrerar en ziljon steg.
Jag skulle kanske ha ersatt den citerade passagen med
”Nu har vi visat att P(p) är sant för alla (positiva heltal) p upp till och med 10. Vi kan fortsätta på samma sätt för alla p upp till och med n oavsett hur stort n är.”
Sedan kan man flasha med termer som induktionsaxiomet, men då kanske man bör googla på det först.
Mogens skrev:”Således kan vi se att om P(n) är sant för ett givet värde på n, så är det också sant för nästa värde på n. Därför, eftersom P(1) är sant, kan vi dra slutsatsen att P(n) är sant för varje n ≥1”
Egentligen vet jag inte om det hjälper att gå upp till 10 eller hundra eller tusen. Du kanske övertygar en skeptisk person, men påståendet blir inte säkrare för att du demonstrerar en ziljon steg.
Jag skulle kanske ha ersatt den citerade passagen med
”Nu har vi visat att P(p) är sant för alla (positiva heltal) p upp till och med 10. Vi kan fortsätta på samma sätt för alla p upp till och med n oavsett hur stort n är.”
Sedan kan man flasha med termer som induktionsaxiomet, men då kanske man bör googla på det först.
Tack för svaret. Men har en till fråga tycker du att själva lösningen ser korrekt ut, asså är själva förklarning godkänd eller ska jag ren skriva den och använda termer som induktionsaxiomet och använda citat som du gav mig? undrar för att jag vill inte för komplicera min lösning.
Jag återkommer till citatet:
”Således kan vi se att om P(n) är sant för ett givet värde på n, så är det också sant för nästa värde på n.”
Din sekvens upp till n = 10 visar ju inte det.
Att P(n) sant => P(n+1) sant har du ju visat tidigare. Vad du gör när du klättrar uppför induktionstrappan är att du utnyttjar [om P(n) sant så P(n+1) sant].
Så den långa harangen i ditt tilltänkta svar (tack ordbehandlare:) tillför ingenting rent logiskt. Och det är inget fel, uppgiften är att övertyga en skeptiker. Hur detta bäst åstadkoms är ju en fråga om tvivlarens psykologi. Dessutom ingick i uppgiften att alla steg t o m 10 skulle skrivas ned, så där har du inga frihetsgrader.
Induktionsaxiomet säger att
OM
P(1) sann
och
P(p) sann => P(p+1) sann. (”A=>B” betyder ”om A så B”)
SÅ
P(n) sann alla (pos heltal) n.
Ett axiom kan inte bevisas. Frågan är om det kan ”förklaras”. Du kan bara försöka övertyga skeptikern om det rimliga i resonemanget. Själv föredrar jag min formulering framför din.
Ordbehandlare förresten. Jag har en misstanke att du kopierade en rad och klistrade in den nio gånger med små ändringar. Det kanske är ett sätt:
Vi vet redan att P(1) är sant. Vi vet då också, genom att sätta p = 1 i det andra antagandet, att P(2) är sant.
Vi vet då också, genom att sätta p = 2 i det andra antagandet, att P(3) är sant.
Vi vet då också, genom att sätta p = … i det andra antagandet, att P(…) är sant.
Vi vet då också, genom att sätta p = … i det andra antagandet, att P(…) är sant.
Vi vet då också, genom att sätta p = … i det andra antagandet, att P(…) är sant.
…
Man kan ju be tvivlaren att tala om på vilken rad det skulle sluta att stämma.
Säg att P(73) är falskt. Men i så fall måste P(72) vara falskt, och P(71), … ned till stegens botten.
Good luck!
