Induktionsbevis - matematisk induktion
Modus ponens - en slutledningsregel
p och q är påståenden.
p \(\Rightarrow \) q betyder p medför q eller om p så q.
Om påståendena p och p \(\Rightarrow \) q är sanna är påståendet q sant.
Exempel
p är påståendet att Kalle bor i Helsingborg. Vi skriver kort
p: Kalle bor i Helsingborg
q är påståendet att Kalle bor i Skåne. Eller kortare q: Kalle bor i Skåne.
p \(\Rightarrow \) q är då påståendet att om Kalle bor i Helsingborg så bor Kalle i Skåne, vilket ju är ett sant påstående. Av detta kan vi inte dra slutsatsen att Kalle bor i Skåne.
Men om det är faktiskt är sant att Kalle bor i Helsingborg kan vi dra slutsatsen att Kalle bor i Skåne.
Induktionsbevis
Vi tänker oss att vi för varje naturligt tal n > 0 har ett påstående \({{p}_{n}}\).
- \({{p}_{1}}\) är sant.
- \({{p}_{n}}\Rightarrow {{p}_{n+1}}\) för alla naturliga tal n > 0.
Då är alla påståendena \({{p}_{n}}\) sanna.
Eftersom \({{p}_{1}}\) är sant och \({{p}_{1}}\Rightarrow {{p}_{2}}\) är \({{p}_{2}}\) sant.
Eftersom \({{p}_{2}}\) är sant och \({{p}_{2}}\Rightarrow {{p}_{3}}\) är \({{p}_{3}}\) sant.
Eftersom \({{p}_{3}}\) är sant och \({{p}_{3}}\Rightarrow {{p}_{4}}\) är \({{p}_{4}}\) sant.
Så här kan man fortsätta så att man når man fram till \({{p}_{n}}\) för varje givet naturligt tal n > 0. Av 1. och 2. följer alltså att \({{p}_{n}}\) är sant för alla naturliga tal n > 0.
Vi har alltså en följd av påståenden som uppfyller att det första är sant samt att varje påstående i följden, utom det första, är en konsekvens av det föregående. Då måste alla påståenden i följden vara sanna.
När man genomför ett induktionsbevis behöver man alltså
- identifiera en följd av påståenden
- bevisa att det första påståendet är sant
- visa att varje påstående utom det första är en konsekvens av det föregående
Ett induktionsbevis
Vi skall bevisa att \(1\text{ }+\text{ }2\text{ }+\text{ }3\text{ }+\text{ }4\text{ }+\text{ }\ldots .\text{ }+n\text{ }=~\dfrac{n\left( n+1 \right)}{2}\) föralla naturliga tal n > 0 med matematisk induktion.
Vi tänker oss denna följd av påståenden:
\({{p}_{1}}:1=\dfrac{1(1+1)}{2}\)
\({{p}_{2}}:1+2=\dfrac{2(2+1)}{2}\)
\({{p}_{3}}:1+2+3=\dfrac{3(3+1)}{2}\)
\(\vdots \)
\({{p}_{n}}:1\text{ }+\text{ }2\text{ }+\text{ }3\text{ }+\text{ }\ldots .\text{ }+n\text{ }=~\dfrac{n\left( n+1 \right)}{2}\)
\({{p}_{n+1}}:1\text{ }+\text{ }2\text{ }+\text{ }3\text{ }+\text{ }\ldots .\text{ }+\text{ }n+\text{ }n+1\text{ }=~\dfrac{\left( n+1 \right)\left( \left( n+1 \right)+1 \right)}{2}=\) \(\dfrac{\left( n+1 \right)\left( n+2 \right)}{2}\)
Vi ser att det första påståendet, \({{p}_{1}}\), är sant. Det är ju ekvivalent med påståendet att 1 = 1.
Vi skall nu visa att varje påstående utom det första är en konsekvens av det föregående d.v.s. \({{p}_{n}}\Rightarrow {{p}_{n+1}}\) för alla naturliga tal n > 0.
\[{{p}_{n}}\Rightarrow 1\text{ }+\text{ }2\text{ }+\text{ }3\text{ }+\text{ }4\text{ }+\text{ }\ldots .\text{ }+n\text{ }=~\dfrac{n\left( n+1 \right)}{2}\Rightarrow \][vi adderar n + 1 till vänster och höger led] \[\Rightarrow 1\text{ }+\text{ }2\text{ }+\text{ }3\text{ }+\text{ }4\text{ }+\text{ }\ldots .\text{ }+n+n+1\text{ }=~\dfrac{n\left( n+1 \right)}{2}+n+1\]= [vi gör liknämnigt i högerledet] \(\dfrac{n(n+1)+2(n+1)}{2}=[ \text{vi bryter ut (}n\text{+1) i t }\!\!\ddot{\mathrm{a}}\!\!\text{ ljaren }\!\!]\!\!\text{ =}\dfrac{(n+1)(n+2)}{2}\) .
Vi har alltså visat att \[{{p}_{n}}\Rightarrow 1\text{ }+\text{ }2\text{ }+\text{ }3\text{ }+\text{ }4\text{ }+\text{ }\ldots .\text{ }+n+n+1\text{ }=~\dfrac{\left( n+1 \right)\left( n+2 \right)}{2}\], d.v.s.\({{p}_{n}}\Rightarrow {{p}_{n+1}}\) .
Uttrycket till höger om pilen är ju precis påståendet \({{p}_{n+1}}\)
Detta innebär att induktionsbeviset är klart.