vollständige Induktion

17.11.2010, 20:49

bandchef

vollständige Induktion

Hi Leute!

Ich soll folgenden Algorithmus mit vollständiger Induktion beweisen:

{n ist eine natürliche Zahl}
begin
q:=0;
for i:=1 to n do
q:=q+2i-1
end
{q=n^2}

Meine Übersetzung in die Mathematik lautet jetzt so:

$\begin{eqnarray*} \sum\limits_{i=1}^n q = n^2 \end{eqnarray*}$

IA und IS hab ich gemacht aber ich bleib jetzt hier beim Beweis hängen: $\begin{eqnarray*} n^2+3n+1 \end{eqnarray*}$

Könnt ihr mir helfen?

17.11.2010, 21:07

bandchef

Auf diesen Beitrag antworten »

Ich hab jetzt noch ein bisschen rumprobiert und dabei auf folgende Formel gestoßen die ich auch beweisen kann:

$\begin{eqnarray*} \sum^n_{i=1} (2i-1) = n^2 \end{eqnarray*}$

$\begin{eqnarray*} \sum^{n+1}_{i=1} (2i-1) = \sum^n_{i=1} (2i-1) + (2(n+1)-1) = n^2 + 2(n+1)-1 = n^2 + 2n +1 = (n+1)^2 \end{eqnarray*}$

Ich weiß nur jetzt nicht warum aus q:=q+2i-1, 2i-1 wird. Laut meines Algorithmus ist ja q:=0 wenn ich dass nun in q:=q+2i-1 einsetze, dann bekomm 0:=2i-1 raus...

Irgendwie versteh ich das nicht...

18.11.2010, 00:27

Mathewolf

Auf diesen Beitrag antworten »

Nein, bekommst du nicht. In deinem Algoritmus initialisierst du die Variable q mit 0. Das gehört sich für eine saubere Variablendeklaration. Damit soll verhindert werden, dass unsinnige Werte in der Variablen stehen, wodurch bei einigen Prpgrammiersprachen böse Dinge geschehen können.
Die eigentliche Reihe bildest du in der For-Schleife.

Bei jedem Durchlauf wird 2i-1 zu q hinzuaddiert. Beim Start des nächsten nächsten Durchlaufs besitzt q den Wert 1. Addiert wird dann 2*2-1=3 damit erhält q den neuen Wert 4. Im Nächsten Durchlauf wird dann 5 hinzuaddiert und man erhält für q den Wert 9. Dieses Spiel geht so weiter, bis n erreicht ist. Zu der Variablen deklaration kommst du doch gar nicht mehr, so dass q wieder auf 0 gesetzt werden könnte.

20.11.2010, 11:50

bandchef

Auf diesen Beitrag antworten »

Ich hab jetzt den Algorithmus mal für ein paar Werte durchgespielt.

q = 0

q = 0+2*1-1 = 1
q = 1

q = 1+2*2-1 = 4
q = 4

q = 4+2*3-1
q = 9

q = 9+2*4-1
q = 16

q = 16+2*5-1
q = 25

usw. usf.

Stimmt das jetzt so?

Was mir daraus nun klar wird, ist der Summenoperator: $\begin{eqnarray*} \sum\limits_{i=1}^n \end{eqnarray*}$

Über welche Funktion aber nun die Summe gebildet werden soll, ist mir leider nicht klar. Ich hab aber trotzdem mal eine Überlegung gemacht. Nämlich so:

$\begin{eqnarray*} \sum\limits_{i=1}^n (2 \cdot i -1)^2 = n^2 \end{eqnarray*}$

Jetzt kann ich für i=3 einsetzen und auf n^2 3 einsetzen und es kommt auf beiden Seiten 9 raus. So sollte es doch jetzt stimmen, oder? Meine Ausgangsform heißt ja q+2*i-1. Warum muss ich das q+ wegtun?

20.11.2010, 13:43

Kawarider90

Auf diesen Beitrag antworten »

die gesuchte summe ist doch einfach $\begin{eqnarray*} \sum\limits_{i=1}^n (2 \cdot i -1)= n^2 \end{eqnarray*}$
du hast ja auch schon bewiesen dass sie auch für n+1 gilt

20.11.2010, 13:46

bandchef

Auf diesen Beitrag antworten »

Ich hab ja die Summe jetzt auch schon da stehen. Jetzt soll ich die Sumem $\begin{eqnarray*} \sum\limits_{i=1}^n (2 \cdot i -1)^2 = n^2 \end{eqnarray*}$ noch durch vollständige Induktion beweisen. IA und IS hab ich schon gemacht und hab die Summe jetzt schon zu $\begin{eqnarray*} n^2+4n^2+4n+1 \end{eqnarray*}$ umgeformt. Jetzt weiß ich aber wieder nicht mehr weiter wie ich das auf meine IV $\begin{eqnarray*} (n+1)^2 \end{eqnarray*}$ hinbringe...

20.11.2010, 14:30

Kawarider90

Auf diesen Beitrag antworten »

weils nicht das selbe ist

20.11.2010, 15:03

bandchef

Auf diesen Beitrag antworten »

Mein erster Lösungsansatz in meinem zweiten Thread war: $\begin{eqnarray*} \sum^n_{i=1} (2i-1) = n^2 \end{eqnarray*}$

Laut Mathewolf stimmt dieser erste Ansatz aber nicht:

Zitat:

Nein, bekommst du nicht.

Kawarider schreibt jetzt, dass $\begin{eqnarray*} \sum\limits_{i=1}^n (2 \cdot i -1)^2 = n^2 \end{eqnarray*}$ falsch ist, aber $\begin{eqnarray*} \sum^n_{i=1} (2i-1) = n^2 \end{eqnarray*}$ stimmt (was konträr zur Aussage von Mathewolf ist. Leute, was stimmt denn jetzt eigentlich? Und wer hat recht?

Wenn ich die Induktion mit meinem ersten Ansatz durchrechne (welcher mit Kawariders Anstoß übereinstimmt) dann komm ich auf meine IV von $\begin{eqnarray*} (n+1)^2 \end{eqnarray*}$ .

Danke!

20.11.2010, 17:15

Mathewolf

Auf diesen Beitrag antworten »

Zitat:

Original von bandchef

Kawarider schreibt jetzt, dass $\begin{eqnarray*} \sum\limits_{i=1}^n (2 \cdot i -1)^2 = n^2 \end{eqnarray*}$ falsch ist, aber $\begin{eqnarray*} \sum^n_{i=1} (2i-1) = n^2 \end{eqnarray*}$ stimmt (was konträr zur Aussage von Mathewolf ist. Leute, was stimmt denn jetzt eigentlich? Und wer hat recht?

Darauf bezog sich meine Aussage nicht. Sie bezog sich auf die Aussage

Zitat:

Original von bandchef

Laut meines Algorithmus ist ja q:=0 wenn ich dass nun in q:=q+2i-1 einsetze, dann bekomm 0:=2i-1 raus...

Den Induktionsschritt hast du richtig vollzogen und den Beweis richtig zuende geführt.

22.11.2010, 21:16

bandchef

Auf diesen Beitrag antworten »

Danke für deine Hilfe!

Neue Frage »

Antworten »

vollständige Induktion

Verwandte Themen