Kleinere Zahlen hinzuzählen

[3_of_8]

Korrekt lautet der Beweis so:

Behauptung:
n
Sigma i = n(n+1)/2
i=1

Induktionsanfang:
1
Sigma i = 1 = 1(1+1)/2
i=1

Induktionsvoraussetzung:

Die Behauptung gilt für alle n in N mit n<=k:

Induktionsschluss:

n+1
Sigma i =
i=1

n
=Sigma + n+1 = n(n+1)/2 + n+1 = (n(n+1)+2n+2)/2 = (n²+3n+2)/2 =
i=1

=(n+1)(n+2)/2

Es folgt: Gilt die Behauptung für alle n in N mit n<=k, dann gilt die Behauptung auch für alle n in N mit n<=k+1.

Es folgt die Gültigkeit der Behauptung für N.

q.e.d.

[Nikolas]

Du hast in so ziemlich allen Summen deine Laufvariable vergessen...

n
sigma = 0
i=1

Warum forderst du denn, dass die Aussage für alle k <=n gilt und was ist eigentlich dieses n? Später benutzt du nur, dass die Aussage für n gilt.

Es reicht zu fordern, dass es für ein (einziges) n in N gilt, wenn man zeigt, dass man daraus auch die Gültigkeit für n+1 zeigen kann und zusätzlich noch explizit zeigt, dass die Aussage für die 1 gilt. (oder die Null, die Formel gilt immer)

[3_of_8]

Ich hab das ganze jetzt nochmal leicht korrigiert.

Also, was ich mache ist das:
Ich beweise erst einmal, dass meine Behauptung für n=1 gilt. (Also für alle n in N mit n<=1).

Anschließend beweise ich (unter der Vorraussetzung, dass die Behauptung für alle n in N mit n<=k gilt), dass die Behauptung auch für alle n in N mit n<=k+1 gilt.

[inherited]

3_of_8: Toll, wie schön dass du das auch kannst. zufrieden?
Nikolas: Ja, und ich fand/finde die Induktionsannahme unwichtig, wobei man das so und so sehen kann.

[Nikolas]

Zitat:

Anschließend beweise ich (unter der Vorraussetzung, dass die Behauptung für alle n in N mit n<=k gilt), dass die Behauptung auch für alle n in N mit n<=k+1 gilt.

a) Warum forderst du, dass die Behauptung für alle n<=k gilt? Diese Vorraussetzung wird nicht benutzt.
b) Wer ist eigentlich dieses k?

BTW: Du zeigst nicht, dass die Behauptung für alle n<=k+1 gilt. Du zeigst ausschließlich, dass sie für n+1 (k+1?) gilt.

@ GrünFisch: Ohne diese Annahme kommst du aber nicht ans Ziel. Und wenn du etwas unter einer unbewiesenen Annahme berechnen willst, musst du die schon angeben.

[3_of_8]

@Nikolas:

Da kommt ja die Induktion ins Spiel.
k ist sozusagen die obere Schranke, für die das ganze gilt.
Beim Induktionsanfang ist k=1. Dann beweise ich, dass es, wenn es für k gilt, auch für k+1 gilt. Also wenn für k=1, dann auch für k=2, dann auch für k=3 usw. Wenn man das bis unendlich fortdenkt, ist es für {1; 2; 3;...}, also ganz N, bewiesen.

@Inherited:

Dann hast du das Verfahren wohl noch nicht so ganz verstanden. Ohne Induktionsannahme funktioniert da nämlich gar nix. Und darum hab ich es auch nochmal korrekt formuliert.

[inherited]

3_of_8: Der Beweis mag ohne nicht komplett sein, aber die Aussage "ohne funktioniert da garnicht" ist schlichtweg falsch.

[Nikolas]

Zitat:

3_of_8: Der Beweis mag ohne nicht komplett sein, aber die Aussage "ohne funktioniert da garnicht" ist schlichtweg falsch.

Da hast du Unrecht. Wenn du nicht explizit vermerkst, dass du diese Annahme triffst, sondern die unbewiesene Aussage einfach benutzt, hast du im Endeffekt gar nichts gezeigt, da du einen logischen Bruch hast. Nur weil die Aussage für n=1 gilt, darfst du sie nicht allgemein einsetzen.

Zitat:

Da kommt ja die Induktion ins Spiel.
k ist sozusagen die obere Schranke, für die das ganze gilt.
Beim Induktionsanfang ist k=1. Dann beweise ich, dass es, wenn es für k gilt, auch für k+1 gilt. Also wenn für k=1, dann auch für k=2, dann auch für k=3 usw. Wenn man das bis unendlich fortdenkt, ist es für {1; 2; 3;...}, also ganz N, bewiesen.

Wie ein Induktion funktioniert, ist mir schon klar, ich habe in den ersten Semestern auch 3-4 MatheVorlesungen (also richtige, nicht die für Informatiker) gehört.

Was du hier schreibst, ist aber nicht das, was du in deinem Beweis geschrieben hast. Der Satz 'Dann beweise ich, dass es, wenn es für k gilt, auch für k+1 gilt.' ist die Kernaussage. Du betrachtest keine Menge von Zahlen, für die die Aussage gilt, sondern nur eine einzige und zeigt, dass es auch für die nächste Zahl gilt.
Deine Vorraussetzung ist zu stark und kann dir bei anderen Beweisen Ärger bringen. Bei einem Satz (ich glaube etwas über Bäume), kann man die Aussage erst für alle zweierPotenzen zeigen und dann die Induktion von n nach n-1 machen und so rückwärts induzieren.
Bei sowas hättest du dann Probleme mit deiner Vorraussetzung.