Vollständige Induktion, mögliche Variante?

19.05.2010, 01:11

dragoneye

Vollständige Induktion, mögliche Variante?

Meine Frage:
Hallo Leute!
Ich habe eine Frage zur vollständigen Induktion. Nehmen wir an ich habe den Induktionsanfang für n=1 UND n=2 erfolgreich geprüft. Nun stelle ich meine Induktionshypothese auf: Die Aussage sei richtig für ein n aus IN und für n-1 aus IN. Nun beweise ich mithilfe der Richtigkeit der Aussage für n und mithilfe der Richtigkeit der Aussage für n-1, dass die Aussage für n+1 richtig ist. Habe ich damit (überhaupt) was bewiesen?

Meine Ideen:
...

19.05.2010, 01:29

Rmn

Auf diesen Beitrag antworten »

RE: Vollständige Induktion, mögliche Variante?
Sobald du auch IA für n=1 UND n=2 nachweisen kannst, dann ja.

19.05.2010, 16:11

dragoneye

Auf diesen Beitrag antworten »

Ich hätte dazu noch eine Frage. Ich habe heute mit jemandem geredet, der mir sagte, es mache bei der vollständigen Induktion keinen Unterschied ob man bei der Induktionshypothese die Richtigkeit der Aussage BIS zu einem n in IN, oder ob man die Richtigkeit der Aussage für nur EIN n in IN annimmt, und man dann den Induktionsschritt von n nach n+1 zeigt. Stimmt das? Dann wäre es ja bei meiner vorherigen Frage auch ausreichend, wenn ich nur für n=1 den Induktionsanfang zeige, und dann meine Aussage beweise, indem ich die Richtigkeit für alle Zahlen bis n und insbesondere die Richtigkeit der Aussage für n-1 annehme, und dann meinen Induktionsschritt von n nach n+1 zeige, oder? Falls ja, wie kann man begründen, dass es keinen Unterschied macht ob ich die Richtigkeit nur für ein n annehme bzw. die Richtigkeit bis n?
Viele Grüße

19.05.2010, 20:19

Evelyn89

Auf diesen Beitrag antworten »

ich hätte auch mal eine frage zu diesem thema.
kann man die vollständige induktion auch für die ganzen Zahlen durchführen?

ich hätte es folgendermaßen gemacht:

1.) analog wie in den natürlichen Zahlen IN, also: I.A.: n=1,
Danach zeig ich den Induktionsschritt n->n+1 mit Hilfe der I.V.

2.) Ich zeige, dass die Aussage für n=0 gilt.

3.) ich zeige: Aussage gilt für n= -1 (I.A.) und dann den Induktionsschritt n-> -n-1
mit Hilfe der I.V.

Ist so etwas okay? Also Induktion für ganze Zahlen zu benutzen oder gibt es da irgendwo einen Haken?

Bin für jede Hilfe dankbar. smile

20.05.2010, 14:21

Evelyn89

Auf diesen Beitrag antworten »

Kann mir echt niemand sagen, ob die Variante so erlaubt ist?

20.05.2010, 15:17

gonnabphd

Auf diesen Beitrag antworten »

Ich wüsste nicht, wieso das falsch sein sollte. Aber: ich zweifle stark daran, ob man damit viel sinnvolles zeigen kann.

Für was willst das denn verwenden?

20.05.2010, 18:51

Evelyn89

Auf diesen Beitrag antworten »

Zum einen interessiert mich, ob das Verfahren logisch korrekt ist und zum zweiten hatte ich vor 2 wochen eine aufgabe zu den tschebyschow-polynomen.
da musste man eine identität für matrizen zeigen, die für alle ganzen Zahlen gelten soll.
Deshalb kam mir die Idee. Leider hab ich die Aufgabe gerade nicht parat, aber wenn du interessiert bist, kann ich sie gerne raussuchen?

20.05.2010, 19:03

Auf diesen Beitrag antworten »

Zitat:

Original von dragoneye
Falls ja, wie kann man begründen, dass es keinen Unterschied macht ob ich die Richtigkeit nur für ein n annehme bzw. die Richtigkeit bis n?
Viele Grüße

Es ist richtig, und es lässt sich folgendermaßen formal logisch begründen:

Wenn du Aussage $\begin{eqnarray*} A_n \end{eqnarray*}$ auf diese Weise beweisen willst, d.h. per Induktionsschritt

$\begin{eqnarray*} (A_k ~ \forall k<n) \to A_n \end{eqnarray*}$ ,

dann kann man das als "normale" Induktion $\begin{eqnarray*} B_{n-1}\to B_n \end{eqnarray*}$ für die Aussage

$\begin{eqnarray*} B_n := \bigwedge_{k=1}^{n-1} A_k \end{eqnarray*}$

auffassen: Im Induktionsschritt zeigt man nämlich aus der Richtigkeit von $\begin{eqnarray*} B_{n-1} \end{eqnarray*}$ die von $\begin{eqnarray*} A_n \end{eqnarray*}$ , und damit ist dann natürlich auch $\begin{eqnarray*} B_n = B_{n-1}\wedge A_n \end{eqnarray*}$ richtig.

20.05.2010, 19:07

dragoneye

Auf diesen Beitrag antworten »

Vielen Dank Arthur Dent, du hast mir sehr geholfen!

20.05.2010, 19:08

gonnabphd

Auf diesen Beitrag antworten »

@ Ev.: Interessiert wäre ich schon, aber dann auch wieder nicht so sehr, dass du deine Zeit mit Suchen usw. verschwenden müsstest Augenzwinkern

...

Aber wie gesagt, dein Verfahren läuft ja letztendlich darauf hinaus zwei (unabhängige) Induktionen zu führen (einmal in positive Richtung und einmal in negative), deshalb sollte es da keine logischen Einwände geben.

20.05.2010, 19:29

Auf diesen Beitrag antworten »

@dragoneye

Nach demselben Prinzip kann man übrigens auch deine erste Anfrage begründen:

Zitat:

Original von dragoneye
Nehmen wir an ich habe den Induktionsanfang für n=1 UND n=2 erfolgreich geprüft. Nun stelle ich meine Induktionshypothese auf: Die Aussage sei richtig für ein n aus IN und für n-1 aus IN. Nun beweise ich mithilfe der Richtigkeit der Aussage für n und mithilfe der Richtigkeit der Aussage für n-1, dass die Aussage für n+1 richtig ist.

Das entspricht dann einem normalen Induktionsbeweis für die Aussage $\begin{eqnarray*} B_n := A_{n-1} \wedge A_n \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ .

Der Induktionsanfang ist dann $\begin{eqnarray*} B_2 = A_1 \wedge A_2 \end{eqnarray*}$ , d.h. es muss sowohl $\begin{eqnarray*} A_1 \end{eqnarray*}$ als auch $\begin{eqnarray*} A_2 \end{eqnarray*}$ nachgewiesen werden, damit die Sache funktioniert - genau das hast du ja laut deinem ersten Satz getan. Augenzwinkern

Neue Frage »

Antworten »

Vollständige Induktion, mögliche Variante?

Verwandte Themen