Vollständige Induktion

Autor: Leandro Alegsa

03-11-2020

Die mathematische Induktion ist eine besondere Art des Nachweises einer mathematischen Wahrheit. Sie kann dazu verwendet werden, um zu beweisen, dass für alle natürlichen Zahlen (alle positiven ganzen Zahlen) etwas wahr ist. Die Idee ist, dass

Für den ersten Fall trifft etwas zu
Dasselbe gilt immer für den nächsten Fall

dann

Dasselbe gilt für jeden Fall

In der sorgfältigen Sprache der Mathematik:

Geben Sie an, dass der Beweis durch Induktion über n {\Darstellungsstil n} erfolgen wird. ( n {\Darstellungsstil n} ist die Induktionsvariable).
Zeigen Sie, dass die Aussage wahr ist, wenn n {\Darstellungsstil n} gleich 1 ist.
Nehmen Sie an, dass die Aussage für jede natürliche Zahl n {\Darstellungsstil n} wahr ist. (Dies wird als Induktionsschritt bezeichnet).

Zeigen Sie dann, dass die Aussage für die nächste Zahl, n + 1 {\darstellungsstil n+1} $n+1$ wahr ist.

Denn es gilt für 1, dann gilt es für 1+1 (=2, durch den Induktionsschritt), dann gilt es für 2+1 (=3), dann gilt es für 3+1 (=4), und so weiter.

Ein Beispiel für den Beweis durch Induktion:

Beweisen Sie dies für alle natürlichen Zahlen n:

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

Beweise:

Zunächst kann die Aussage geschrieben werden: für alle natürlichen Zahlen n

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

Durch Induktion auf n,

Erstens, für n=1:

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

Das ist also wahr.

Nehmen Sie als nächstes an, dass für einige n=n0 die Aussage wahr ist. Das heißt:

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

Dann für n=n0+1:

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

kann umgeschrieben werden

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

Seit 2 ∑ k = 1 n 0 k = n 0 ( n 0 + 1 ) , {\darstellungsstil 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 ) {\darstellungsstil 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)} {\darstellungsstil 2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)} $2\sum _{k=1}^{n_{0}+1}k=n_{0}(n_{0}+1)+2(n_{0}+1)=(n_{0}+1)(n_{0}+2)$

Daher ist der Beweis richtig.

Induktive Definition

Dieselbe Idee kann sowohl zur Definition als auch zum Nachweis dienen.

Definieren Sie n {\Darstellungsstil n} den Grad Cousin:

Ein Cousin 1. $1$ Grades ist das Kind eines Geschwisters eines Elternteils
Ein n + 1 {\Darstellungsstil n+1} $n+1$ st Grad Cousin ist das Kind eines n {\Darstellungsstil n} st Grad Cousins eines Elternteils.

Es gibt eine Reihe von Axiomen für die Arithmetik der natürlichen Zahlen, die auf mathematischer Induktion beruht. Dies wird "Peano's Axiome" genannt. Die undefinierten Symbole sind | und =. Die Axiome sind

| ist eine natürliche Zahl
Wenn n {\Darstellungsstil n} eine natürliche Zahl ist, dann ist n | {\Darstellungsstil n|} $n|$ eine natürliche Zahl
Wenn n | = m | {\Anzeigestil n|=m|} $n|=m|$ dann n = m {\Anzeigestil n=m} $n=m$

Man kann dann die Operationen der Addition und Multiplikation usw. durch mathematische Induktion definieren. Zum Beispiel:

m + | | = m | {\Anzeigestil m+|=m|} $m+|=m|$
m + n | = ( m + n ) | | {\Anzeigeart m+n|=(m+n)|} $m+n|=(m+n)|$

Fragen und Antworten

F: Was ist mathematische Induktion?

A: Die mathematische Induktion ist eine besondere Art des Beweises einer mathematischen Wahrheit, mit der man beweisen kann, dass etwas für alle natürlichen Zahlen oder positiven Zahlen ab einem bestimmten Punkt wahr ist.

F: Wie läuft der Beweis durch Induktion ab?

A: Der Beweis durch Induktion geht typischerweise so vor, dass man festlegt, dass der Beweis über n durchgeführt wird, zeigt, dass die Aussage wahr ist, wenn n gleich 1 ist, nimmt an, dass die Aussage für jede natürliche Zahl n wahr ist, und zeigt dann, dass sie für die nächste Zahl (n+1) wahr ist.

F: Was bedeutet es, in einem induktiven Schritt etwas anzunehmen?

A: Etwas in einem induktiven Schritt anzunehmen bedeutet, es als wahr zu akzeptieren, ohne einen Beweis zu erbringen oder zu beweisen. Sie dient als Ausgangspunkt für weitere Untersuchungen.

F: Welche Art von Zahlen werden bei der mathematischen Induktion verwendet?

A: Bei der mathematischen Induktion werden typischerweise natürliche Zahlen oder ab einem bestimmten Punkt positive Zahlen verwendet.

F: Wie zeigt man, dass etwas für die nächste Zahl (n+1) wahr ist?

A: Um zu zeigen, dass etwas für die nächste Zahl (n+1) wahr ist, müssen Sie zuerst beweisen, dass es wahr ist, wenn n=1 ist, und dann Ihre Annahme aus dem induktiven Schritt verwenden, um zu zeigen, dass es auch für n+1 wahr ist.