Beweis durch vollständige Induktion

17.11.2004, 23:07

Moeki

Beweis durch vollständige Induktion

Zitat:

Man beweise, dass für alle natürliche Zahlen gilt:

1 + 3 + 5 + .. + (2n-1) = n²!

Mit an Sicherheit grenzender Wahrscheinlichkeit wird dieser Satz durch vollständige Induktion bewiesen, nur leider war ich in der entsprechenden Vorlesung wegen einer Überschneidung nicht da. Weder im Buch noch bei den Mitstudenten finde ich den erhofften Rat und zur Übung kann ich morgen auch nicht.

Kann mir jemand vielleicht diesbezüglich auf die Sprünge helfen und an oben genannten Beispiel die Beweisführung (vollständige Induktion) erklären?

Danke, Marko.

17.11.2004, 23:29

TomBombadil

Auf diesen Beitrag antworten »

Hmmm....

Als erstes sollstest du die Anfangsbedingung beweisen.

n = 1

Das für stimmt die Behauptung offensichtlich.

1 = $\begin{eqnarray*} 1^{2} \end{eqnarray*}$

Nun kommt der Induktionsschritt:

Es wird angenommen für ein k sei die Behauptung bewiesen:

Also 1+3+5+7.....+ (2k-1) = $\begin{eqnarray*} k^{2} \end{eqnarray*}$

Um nun den Induktionsschluß zu machen mußt du zeigen, dass das auch für
k+1 gilt.

Also:

1+3+5+7+.....(2k-1)+(2(k+1)-1) = $\begin{eqnarray*} (k+1)^{2} \end{eqnarray*}$

Für die Zahlen 1+3+5+7+.....(2k-1) können wir ja nach Induktionsschritt gleich $\begin{eqnarray*} k^{2} \end{eqnarray*}$ schrieben.

Also : $\begin{eqnarray*} k^{2} + (2k +1) \end{eqnarray*}$ und das ist mit der 1. Binomishcne Formel gleich $\begin{eqnarray*} (k+1)^{2} \end{eqnarray*}$

Ich hoffe ich habe keinen Fehler gemacht.

Da wir nun allgemein bewiesen haben: Wenn für eine Zahl k die Behauptung bewiesen ist, dann ist sie auch für k+1 bewiesen.
Wir haben den Fall k = n = 1 direkt bewiesen, somit (über die Induktion) gilt die Behauptung für k=n=2. aber somit auch für 3 (hier ist k = 2, und k+1 = 3 usw. für alle Elemnte von N.

Hoffe das hat dir weitergeholfen

17.11.2004, 23:40

rnd0m

Auf diesen Beitrag antworten »

RE: Beweis durch vollständige Induktion
1+3+5+ ... +(2n-1) = n²

n=1:

1=1²=1 => stimmt für n=1

n+1:

z.Z.
1+3+5+ ... +(2n-1)+(2(n+1)-1) = (n+1)² wenn 1+3+5+ ... +(2n-1) = n²

1+3+5+ ... +(2n-1)+(2(n+1)-1) =
n² + (2(n+1)-1) =
n² + (2n+2-1) =
n² + 2n + 1 =
(n + 1)²

q.e.d.

18.11.2004, 00:55

riwe

Auf diesen Beitrag antworten »

RE: Beweis durch vollständige Induktion
das geht auch so:

$\begin{eqnarray*} s = 1 + 3 + .....+ (2n-1) \end{eqnarray*}$
$\begin{eqnarray*} s = (2n-1) + (2n-3) +.....+ 1 \end{eqnarray*}$

$\begin{eqnarray*} 2s = 2n \cdot ( 1 + 1 +.... +1) \end{eqnarray*}$

$\begin{eqnarray*} 2\cdot s=2\cdot n^{2} \Rightarrow s=n^{2} \end{eqnarray*}$

werner

18.11.2004, 13:21

Steve_FL

Auf diesen Beitrag antworten »

ich möchte zusätzlich noch auf die Suchen-Funktion verweisen, da dieses Beispiel nicht zum ersten Mal gestellt wird.
Zudem hat Deakandy einen Workshop zur vollständigen Induktion erstellt.

18.11.2004, 22:39

Moeki

Auf diesen Beitrag antworten »

Können wir anhand folgender Aufgabe bitte mal gucken, ob ich das soweit verstanden habe?

Zitat:

Man beweise, dass für alle natürliche Zahlen n >= n0 gilt:

2^n > 2n

und bestimme n0 $\begin{eqnarray*} \in \end{eqnarray*}$ |N (natürliche Zahlen )

Offensichtlich ist n0 = 3.

Denn 2² = 2*2 und 2³ > 2*3 .

Also ist mein Induktionsanfang:

IA 2³ = 8 > 2*3 = 6 und das ist wahr.

Die Induktionsvorraussetzung:

IV 2^k > 2*k

Die Induktionsbehauptung n= k+1

IBH 2^(k+1) > 2 * (k+1)

Diesen letzten Satz muss ich doch jetzt beweisen indem ich die IV einsetze und dann ist gut oder?

18.11.2004, 23:02

Calvin

Auf diesen Beitrag antworten »

Beim Induktionsschritt mußt du 2^(k+1) ein bißchen umformen, und mit Hilfe der Induktionsvorraussetzung den Ausdruck nach unten abschätzen. D.h. du mußt ihn immer ein Stückchen kleiner machen, bis irgendwann 2*(k+1) dasteht. Hast du eine Idee, wie du drauf kommen könntest?

Ich gebe dir mal ein bißchen was vor Augenzwinkern

$\begin{eqnarray*} 2^{k+1} = \ldots \stackrel{I.V.}{>} \ldots > \ldots = 2(k+1) \end{eqnarray*}$

18.11.2004, 23:05

Moeki

Auf diesen Beitrag antworten »

18.11.2004, 23:13

Calvin

Auf diesen Beitrag antworten »

Ich gebe zu, für solche Dinge braucht man ein bißchen Übung. Aber es sieht so aus, als könntest du mit meinem Posting gar nichts anfangen. Deshalb hier mal ausnahmensweise die Lösung. Möglicherweise verstehst du dann die Rangehensweise:

$\begin{eqnarray*} 2^{k+1}=2^k*2 \stackrel{I.V.}{>} 2*k*2 > 2k+2 = 2(k+1) \end{eqnarray*}$

Du siehst, ich habe 2^(k+1) durch ein bißchen Umformen mit Hilfe der Induktionsvorraussetzung immer ein bißchen kleiner gemacht. Von links nach rechts gelesen steht dann 2^(k+1) > 2(k+1) da, was zu beweisen war.

Verstehst du jetzt, wie meine Erklärung gemeint war?

18.11.2004, 23:32

Moeki

Auf diesen Beitrag antworten »

wenn man A^(b+c) mit A^b * A^c auflösen kann, dann ja.

19.11.2004, 14:52

Calvin

Auf diesen Beitrag antworten »

Ja, das gilt allgemein.

24.11.2004, 17:33

Tovok7

Auf diesen Beitrag antworten »

Zitat:

Original von Calvin
$\begin{eqnarray*} 2*k*2 > 2k+2 \end{eqnarray*}$

Und diesen Schritt darf man einfach so ohne Beweis annehmen?

24.11.2004, 18:24

Calvin

Auf diesen Beitrag antworten »

@Tovok7
War das eine Frage, weil du es nicht wußtest? Oder wolltest du nur von mir wissen, dass ich mir bei diesem Schritt wirklich sicher bin?

Da nach dem Induktionsanfang k>=3 ist und die folgende Rechnung unter dieser Vorraussetzung gemacht wird, darf man das in diesem Fall IMHO schon. Ich hätte es evtl. noch dazuschreiben müssen, dass k>=3 ist. Mit einem weiteren Zwischenschritt kann man sagen, dass $\begin{eqnarray*} 2*k*2=(2*k)+(2*k)>2*k+2 \end{eqnarray*}$

Dass die Aussage für k<3 nicht stimmt, ist nicht zu leugnen Augenzwinkern

24.11.2004, 18:43

Tovok7

Auf diesen Beitrag antworten »

Zitat:

Original von Calvin
@Tovok7
War das eine Frage, weil du es nicht wußtest? Oder wolltest du nur von mir wissen, dass ich mir bei diesem Schritt wirklich sicher bin?

Beides, denke ich smile

Zitat:

Original von Calvin
Ich hätte es evtl. noch dazuschreiben müssen, dass k>=3 ist.

OK, wenn man das dazu annimmt, macht der Schritt natuerlich Sinn.

Neue Frage »

Antworten »

Beweis durch vollständige Induktion

Verwandte Themen