Induktionsbevis - matematisk induktion

Modus ponens - en slutledningsregel

p och q är påståenden.

p \(\Rightarrow \) q betyder p medför q eller om pq.

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}}\).

  1. \({{p}_{1}}\) är sant.  
  2. \({{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.