Matematisk induktion | särskilt sätt att bevisa en matematisk sanning

Matematisk induktion är ett speciellt sätt att bevisa en matematisk sanning. Det kan användas för att bevisa att något är sant för alla naturliga tal (eller alla positiva tal från en punkt och framåt). Tanken är att om:

Detta gäller för det första fallet (basfallet);
När samma sak är sann för ett fall, är det också sant för nästa fall (induktivt fall),

sedan

Samma sak gäller för varje fall genom induktion.

På matematikens försiktiga språk går ett bevis genom induktion ofta till på följande sätt:

Ange att beviset kommer att vara genom induktion över n {\displaystyle n} . ( n {\displaystyle n} är induktionsvariabeln.)
Visa att påståendet är sant när n {\displaystyle n} är 1.
Anta att påståendet är sant för alla naturliga tal n {\displaystyle n} . (Detta kallas induktionssteget.)

Visa då att påståendet är sant för nästa tal, n + 1 {\displaystyle n+1} $n+1$ .

Eftersom det är sant för 1, så är det sant för 1+1 (=2, genom induktionssteget), så är det sant för 2+1 (=3), så är det sant för 3+1 (=4) och så vidare.

Exempel på bevis genom induktion

Summan av de första n naturliga talen

Visa att för alla naturliga tal n:

1 + 2 + 3 + . . . . + ( n - 1 ) + n = 1 2 n ( n + 1 ) {\displaystyle 1+2+3+....+(n-1)+n={\tfrac {1}{2}}}n(n+1)} $1+2+3+....+(n-1)+n={\tfrac {1}{2}}n(n+1)$

Bevis:

För det första kan påståendet skrivas som:

2 ∑ k = 1 n k = n ( n + 1 ) {\displaystyle 2\sum _{k=1}^{n}k=n(n+1)} $2\sum _{k=1}^{n}k=n(n+1)$ (för alla naturliga tal n)

Genom induktion på n,

Först för n=1:

2 ∑ k = 1 1 k = 2 ( 1 ) = 1 ( 1 + 1 ) {\displaystyle 2\sum _{k=1}^{1}k=2(1)=1(1+1)} $2\sum _{k=1}^{1}k=2(1)=1(1+1)$ ,

så detta är sant.

Anta sedan att påståendet är sant för vissa n=n₀ . Det vill säga:

2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) {\displaystyle 2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1)$

För n=n₀ +1:

2 ∑ k = 1 n 0 + 1 k {\displaystyle 2\sum _{k=1}^{{n_{0}}}+1}k} $2\sum _{k=1}^{{n_{0}}+1}k$

kan skrivas om till

2 ( ∑ k = 1 n 0 k + ( n 0 + 1 ) ) {\displaystyle 2\left(\sum _{k=1}^{n_{0}}}k+(n_{0}+1)\right)} $2\left(\sum _{k=1}^{n_{0}}k+(n_{0}+1)\right)$

Eftersom 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\displaystyle 2\sum _{k=1}^{n_{0}}}k=n_{0}(n_{0}+1),} $2\sum _{k=1}^{n_{0}}k=n_{0}(n_{0}+1),$

2 ∑ k = 1 n 0 + 1 k = n 0 ( n 0 + 1 ) + 2 ( n 0 + 1 ) = ( n 0 + 1 ) ( n 0 + 2 ) {\displaystyle 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Därför är beviset fullständigt genom induktion.

Summan av de inre vinklarna i en polygon.

Matematisk induktion anges ofta med startvärdet 0 (snarare än 1). I själva verket fungerar det lika bra med en mängd olika startvärden. Här är ett exempel när startvärdet är 3: "Summan av de inre vinklarna i en polygon med n {\displaystyle n} -sidor är ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ grader."

Det ursprungliga startvärdet är 3, och de inre vinklarna i en triangel är ( 3 - 2 ) 180 {\displaystyle (3-2)180} $(3-2)180$ grader. Antag att de inre vinklarna i en polygon med n {\displaystyle n} -sidor är ( n - 2 ) 180 {\displaystyle (n-2)180} $(n-2)180$ grader. Lägg till en triangel som gör figuren till en n + 1 {\displaystyle n+1} $n+1$ -sidig polygon, vilket ökar antalet vinklar med 180 grader ( n - 2 ) 180 + 180 = ( n + 1 - 2 ) 180 {\displaystyle (n-2)180+180=(n+1-2)180} $(n-2)180+180=(n+1-2)180$ grader. Eftersom både grundfallet och det induktiva fallet har behandlats är beviset nu komplett.

Det finns många matematiska objekt för vilka bevis genom matematisk induktion fungerar. Den tekniska termen är en välordnad mängd.

Induktiv definition

Samma idé kan användas för att definiera en uppsättning objekt och för att bevisa påståenden om denna uppsättning objekt.

Vi kan till exempel definiera n {\displaystyle n} kusiner av tredje graden på följande sätt:

En kusin i 1 {\displaystyle 1} $1$ är ett barn till en förälders syskon.
En kusin av n + 1 {\displaystyle n+1} $n+1$ e grad är ett barn till en förälders kusin av n {\displaystyle n} e grad.

Det finns en uppsättning axiom för aritmetiken för de naturliga talen som bygger på matematisk induktion. Detta kallas "Peanos axiom". De odefinierade symbolerna är | och =. Axiomen är följande

| är ett naturligt tal.
Om n {\displaystyle n} är ett naturligt tal, är n | {\displaystyle n|} $n|$ ett naturligt tal.
Om n | = m | {\displaystyle n|=m|} $n|=m|$ så är n = m {\displaystyle n=m} $n=m$ .

Man kan sedan definiera operationerna addition och multiplikation och så vidare genom matematisk induktion. Till exempel:

m + | = m | {\displaystyle m+|=m|} $m+|=m|$
m + n | = ( m + n ) | {\displaystyle m+n|=(m+n)|} $m+n|=(m+n)|$

Relaterade sidor

Matematiskt bevis
Bevis genom motsägelse

Frågor och svar

F: Vad är matematisk induktion?

S: Matematisk induktion är ett särskilt sätt att bevisa en matematisk sanning som kan användas för att bevisa att något är sant för alla naturliga tal eller positiva tal från en viss punkt och framåt.

F: Hur går beviset genom induktion till?

S: Ett induktionsbevis går vanligtvis till så att man anger att beviset kommer att göras över n, visar att påståendet är sant när n är 1, antar att påståendet är sant för alla naturliga tal n och visar sedan att det är sant för nästa tal (n+1).

F: Vad innebär det att anta något i ett induktivt steg?

S: Att anta något i ett induktivt steg innebär att man accepterar det som sant utan att ge bevis eller bevis. Det tjänar som en utgångspunkt för vidare undersökningar.

F: Vilken typ av tal används vid matematisk induktion?

S: I matematisk induktion används vanligtvis naturliga tal eller positiva tal från och med en viss punkt.

F: Hur visar man att något är sant för nästa tal (n+1)?

Svar: För att visa att något är sant för nästa tal (n+1) måste du först bevisa att det är sant när n=1 och sedan använda ditt antagande från det induktiva steget för att visa att det också är sant för n+1.