Induktion über natürliche Zahlen unterschiedlicher IA

26.03.2014, 16:28

Nighel123

Induktion über natürliche Zahlen unterschiedlicher IA

Hi,

Reicht es eigentlich aus für eine Behauptung $\begin{eqnarray*} B \end{eqnarray*}$ die für alle natürliche Zahlen größer einer bestimmten natürlichen Zahl bewiesen werden soll, immer mit dem Induktionsanfang 0 anzufangen?

Sprich soll beweisen werden $\begin{eqnarray*} \forall n : 1 \leq n \rightarrow Bn \end{eqnarray*}$ , dann brauch ich doch keine Induktion mit dem Induktionsanfang 1 machen, sondern kann gleich mit dem Induktionsschritt weiter machen. Warum wird dann in so machem Lehrbuch bei dem $\begin{eqnarray*} 0 \in \mathbb N \end{eqnarray*}$ für Behauptungen mit $\begin{eqnarray*} 1 \leq n \end{eqnarray*}$ immer mit dem Induktionsangang n=1 gemacht?

26.03.2014, 16:36

weisbrot

Auf diesen Beitrag antworten »

RE: Induktion über natürliche Zahlen unterschiedlicher IA

Zitat:

dann brauch ich doch keine Induktion mit dem Induktionsanfang 1 machen, sondern kann gleich mit dem Induktionsschritt weiter machen.

nein! es gibt zahlreiche gegenbeispiele (falsche aussagen, bei denen jedoch der induktionsschritt zutrifft; der ind.anfang aber eben nicht), ich weiß nur aus dem kopf keins Augenzwinkern

Zitat:

Warum wird dann in so machem Lehrbuch bei dem $\begin{eqnarray*} 0 \in \mathbb N \end{eqnarray*}$ für Behauptungen mit $\begin{eqnarray*} 1 \leq n \end{eqnarray*}$ immer mit dem Induktionsangang n=1 gemacht?

man macht den induktionsanfang für die kleinste zahl, für die die aussage bewiesen werden soll, dort also bei n=1.

ich bin mir nicht sicher ob ich genau verstanden hab was das problem ist, hoffe aber dass das trotzdem die frage beantwortet, ansonsten frag nochmal.

lg

26.03.2014, 16:43

10001000Nick1

Auf diesen Beitrag antworten »

RE: Induktion über natürliche Zahlen unterschiedlicher IA

Zitat:

Original von weisbrot

Zitat:

dann brauch ich doch keine Induktion mit dem Induktionsanfang 1 machen, sondern kann gleich mit dem Induktionsschritt weiter machen.

nein! es gibt zahlreiche gegenbeispiele (falsche aussagen, bei denen jedoch der induktionsschritt zutrifft; der ind.anfang aber eben nicht), ich weiß nur aus dem kopf keins Augenzwinkern

Meinst du vielleicht sowas?
Alle Zahlen der Form $\begin{eqnarray*} n+0,5 \text{ mit }n\in\mathbb{N} \end{eqnarray*}$ sind natürliche Zahlen.
Denn: Falls die Behauptung für ein $\begin{eqnarray*} k\in\mathbb{N} \end{eqnarray*}$ zutrifft, also $\begin{eqnarray*} k+0,5\in\mathbb{N} \end{eqnarray*}$ , dann ist auch $\begin{eqnarray*} (k+1)+0,5=\underbrace{(k+0,5)}_{\in\mathbb{N}}+1\in\mathbb{N}. \end{eqnarray*}$

smile

26.03.2014, 17:14

weisbrot

Auf diesen Beitrag antworten »

RE: Induktion über natürliche Zahlen unterschiedlicher IA
@nick: naja, ich meinte eher behauptungen, denen man nicht auf den ersten blick ansieht, dass sie quatsch sind. man kann natürlich auch sowas nehmen, wie: "alle nat. zahlen sind nicht gleich 1 (oder 0, jenachdem)." - als allerdümmstes beispiel.
lg

26.03.2014, 17:19

Iorek

Auf diesen Beitrag antworten »

Behauptung: für alle $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ gilt: $\begin{eqnarray*} 10\mid 9^n \end{eqnarray*}$ .

Springen wir mal direkt zum Induktionsschritt: $\begin{eqnarray*} n\rightarrow n+1 \end{eqnarray*}$ , dann ist also zu zeigen: $\begin{eqnarray*} 10\mid 9^{n+1} \end{eqnarray*}$ .

Da $\begin{eqnarray*} 9^{n+1}=9^n\cdot 9 \end{eqnarray*}$ und nach Induktionsvoraussetzung $\begin{eqnarray*} 10\mid 9^n \end{eqnarray*}$ gilt, gilt also auch $\begin{eqnarray*} 10\mid 9^n\cdot 9 \end{eqnarray*}$ .

Hattest du an solchen Unfug gedacht? Augenzwinkern

Die Teilbarkeitsaussage lässt sich natürlich entsprechend umformulieren, sodass man nicht von vornherein sagen kann, ob das jetzt richtig oder falsch ist.

27.03.2014, 00:58

Nighel123

Auf diesen Beitrag antworten »

Also ich meine natürlich nicht, dass man den Induktionsanfang weglässt, aber dass dieser einfach sofort gilt weil ja die Bedingung $\begin{eqnarray*} n \geq 1 \end{eqnarray*}$ für n=0 nicht erfüllt ist.

Als Beispiel:
Sei $\begin{eqnarray*} Pn : \leftrightarrow ( n \geq 1 \rightarrow \exists j S(j)=n ) \end{eqnarray*}$ (wobei S die Nachfolgerfunktion ist).
Will man zeigen, dass
$\begin{eqnarray*} \forall n Pn \end{eqnarray*}$ , so kann man das machen indem man
zeigt, dass $\begin{eqnarray*} P0 \wedge \forall n (Pn \rightarrow PS(n)) \end{eqnarray*}$

Nun gilt ja P0 direkt, weil $\begin{eqnarray*} \mathfrak F \rightarrow ... \end{eqnarray*}$ immer wahr ist (das meinte ich mit weglassen).

Jetzt wird aber in dem Buch dass ich lese gezeigt, dass $\begin{eqnarray*} P1 \wedge \forall n (Pn \rightarrow PS(n)) \end{eqnarray*}$ .

Meine Frage wahr nun inwiefern das von nutzen ist, denn eigentlich kann man sich ja den Induktionsanfang "sparen", weil die Beh für P0 ja immer wahr ist.

Auf der anderen Seite Frage ich mich, ob dann nicht alle Aussagen $\begin{eqnarray*} A \end{eqnarray*}$ bei denen $\begin{eqnarray*} A0 \end{eqnarray*}$ nicht gezeigt werden kann, aber dafür der Induktionsschritt, einfach abgeändert werden können zu $\begin{eqnarray*} n>0 \rightarrow An \end{eqnarray*}$ , und dann durch Induktion bewiesen werden können.

Gruß Nickel

27.03.2014, 09:06

HAL 9000

Auf diesen Beitrag antworten »

Irgendwie geht es doch bei dieser Diskussion um das Prinzip

Zitat:

Zum Beweis einer Aussage $\begin{eqnarray*} A(n) \end{eqnarray*}$ für alle natürlichen Zahlen $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ genügt es,

a) den Induktionsanfang $\begin{eqnarray*} A(n_0) \end{eqnarray*}$ , und

b) den Induktionsschritt $\begin{eqnarray*} A(n)\to A(n+1) \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ zu zeigen.

Das folgt direkt aus dem "normalen" Induktionsprinzip (d.h. dem mit Start bei Index 0), indem man jenes auf die indexverschobene Aussage $\begin{eqnarray*} B(n) = A(n+n_0) \end{eqnarray*}$ anwendet - fertig.

Wichtig ist, dass man bei dem Prinzip oben auch wirklich sorgsam a),b) einhält. Beispielsweise kann man zwar bei der Aussage

$\begin{eqnarray*} A(n):\; 2^n \geq 3n-1 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$

den Induktionsanfang $\begin{eqnarray*} A(1) \end{eqnarray*}$ nachweisen, und ebenso den Induktionsschritt $\begin{eqnarray*} A(n)\geq A(n+1) \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ bewältigen ... aber das reicht nicht: Denn $\begin{eqnarray*} A(2) \end{eqnarray*}$ selbst ist falsch!

Also nix "weglassen"! Auch wenn im speziellen Fall mal der Induktionsanfang trivial im Nachweis ist, ist das noch lange kein Grund, ihn deswegen wegzulassen. Vor allem darf keine "Lücke" wie im Beispiel eben auftreten, ein häufiger Fehler bei Induktionsbeweis(versuch)en.

28.03.2014, 12:53

weisbrot

Auf diesen Beitrag antworten »

@nighel: es stimmt, dass der IA in soeinem fall trivialerweise stimmt. aber im induktionsschritt musst du von n auf n+1 schließen, das schließt den schritt von 0 auf 1 ein, und das könnte schwierig werden in diesem fall.
und deswegen fängt man einfach gleich mit n=1 an, und kann dan im IS n>0 annehmen.
lg

Neue Frage »

Antworten »

Induktion über natürliche Zahlen unterschiedlicher IA

Verwandte Themen