| Autor |
Beitrag |
    
Sabrina (Guybrush)
| | Veröffentlicht am Donnerstag, den 11. Januar, 2001 - 18:23: | 
|
Also ich weiss, dass man 2 teilt n^2 - n mittels vollstaendiger Induktion beweisen muss, aber ich weiss nicht, wie das gehen soll, da ich die Induktion nur mit linker und rechter Seite kenne ! Kann mir das bitte jemand erklaeren ? Das waere wirklich super ! |
IQzero
| | Veröffentlicht am Donnerstag, den 11. Januar, 2001 - 19:08: |
|
Hi Sabrina!
Ich vermute mal den Induktionsanfeng bekommst Du hin. Hier ist der Induktionsschritt:
2 | n² - n
=> 2 | n² - n + 2n
{ da 2n ist muss die Zahl immer noch gerade sein wenn ich 2n dazuzähle }
=> 2 | n² + 2n + 1 - n - 1
{ das selbe wie oben, nur anders aufgeschrieben }
=> 2 | (n+1)² - (n+1)
q.e.d.
Ich hoffe Du kannst das nachvollziehen. Falls Du Dich fragst wie man darauf kommt, dass man ausgerechnet 2n dazuzählen muss: Du überlegst Dir zuerst wo Du denn hinkommsn willst, also auf (n+1)²-(n+1) und vergleichst das mit n²-n . Nach Anwendung der bin.Formel sieht man dann, dass genau 2n fehlen, und das ist glücklicherweise immer eine gerade Zahl.
Falls Du noch Fragen hast, meld Dich einfach. |
Sabrina (Guybrush)
| | Veröffentlicht am Donnerstag, den 11. Januar, 2001 - 21:31: |
|
Vielen Dank schon mal ! Aber kannst Du mir bitte noch mal den Schluss erklären ? Warum ist 2 / (n+1)^2 - (n+1) der gewünschte Beweis ?
Irgendwie versteh ich gar nicht, was das alles soll !
Kannst Du so lieb sein und mir alle Schritte noch mal genau erklären, also wie man darauf kommt und was das alles dann überhaupt bringt ? Das wäre super !
Sabrina |
IQzero
| | Veröffentlicht am Donnerstag, den 11. Januar, 2001 - 23:26: |
|
Hi Sabrina!
Du musst Dir ganz genau klar machen, wie ein Beweis durch vollständige Induktion überhaupt funktioniert. Nimm mal z.B. die Folge der ungeraden Zahlen 1, 3, 5, 7, 9, ... Die Summe der ersten n Folgenglieder ist immer eine Quadratzahl:
1 = 1²
1 + 3 = 2²
1 + 3 + 5 = 3²
1 + 3 + 5 + 7 = 4²
....................
Das wollen wir mal mit vollständiger Induktion beweisen. Ich habe oben die ersten 4 von unendlich vielen Gleichungen aufgeschrieben, die wir beweisen wollen. Da wir nicht unendlich viele Beweise dazu machen möchten numerieren wir die Aussagen einfach durch:
A(1): 1 = 1²
A(2): 1 + 3 = 2²
A(3): 1 + 3 + 5 = 3²
A(4): 1 + 3 + 5 + 7 = 4²
usw.
Jetzt zeigen wir nur zwei Dinge:
Erstens: Die Aussage A(1) ist richtig! (Induktionsanfang)
Zweitens: Wenn A(n) richtig ist, dann ist auch A(n+1) richtig! (Induktionsschritt)
Wenn das gelingt, dann haben wir damit unendlich viele Aussagen gezeigt, A(n) ist richtig für jedes beliebige n aus N.
Warum ist das so? Sollte jemand beispielsweise an der Aussage A(4) zweifeln, dann können wir ihm sagen, dass A(1) auf alle Fälle richtig ist, da wir den Induktionsanfang gemacht haben. Mit Hilfe des Induktionsschrittes lässt sich dann zeigen: A(1) => A(2), also wissen wir A(2) muss auch stimmen. Wenn wir nun A(2) vertrauen, dann können wir wieder mit dem Induktionsschritt A(3) aus A(2) folgern. Nun müssen wir den Induktionsschritt ein letztes mal bemühen um aus A(3) A(4) zu folgern.
Diese Vorgehensweise lässt sich gedanklich für jede beliebige Aussage A(n) mit einem beliebig grossen anwenden. A(n) muss dann also für alle n wahr sein.
Wichtig ist also nur der Induktionsanfang: A(1) muss gelten,
und der Induktionsschritt: A(n) => A(n+1) muss sich zeigen lassen.
Für das Beispiel bedeutet das konkret:
Behauptung: A(n): 1 + 3 + 5 + ... + 2n-1 = n²
Beweis durch vollständige Induktion:
Induktionsanfang:
Die Aussage ist für n=1 trivialerweise erfüllt, denn es gilt:
1 = 1²
{ A(1) stimmt also }
Induktionsschritt von n -> n+1:
Wir nehmen an die Aussage gelte bereits für alle Zahlen die kleiner oder gleich n sind, dann gilt:
1 + 3 + 5 + ... + 2n-1 + 2n+1
= n² + 2n+1
{ Da wir annehmen dürfen, dass A(n) gilt dürfen wir statt 1+3+5+...+2n-1 auch n² schreiben und bin.Formel anwenden }
= (n+1)²
{ Wir haben nun gezeigt: Wenn wir zu unsrer Summe die nächste ungerade Zahl dazuzählen, dann ergibt sich auch die nächste Quadratzahl }
also A(n) => A(n+1) ist gelungen!
Bei Deiner Aufgabe ist die Aussage:
2 | n² - n
stell Dir auch hier wieder unendlich viele Aussagen vor:
A(1): 2 | 1² - 1 { also 2|0 ist richtig }
A(2): 2 | 2² - 2 { also 2|2 ist richtig }
A(3): 2 | 3² - 3 { also 2|6 ist richtig }
A(4): 2 | 4² - 4 { also 2|12 ist richtig }
.
.
.
A(n) = 2 | n² - n
A(n+1) = 2 | (n+1)² - (n+1)
Wenn Du die Aussage mit vollständiger Induktion beweisen möchtest, zeigst Du auch hier wieder:
Erstens: A(1) stimmt ( 2 | 1² - 1 stimmt)
Zweitens: A(n) => A(n+1)
also aus: 2 | n² - n
folgt: 2 | (n+1)² - (n+1)
Hier ist der Beweis dafür nochmal:
2 | n² - n
=> 2 | n² - n + 2n
{ da 2n ist muss die Zahl immer noch gerade sein wenn ich 2n dazuzähle }
=> 2 | n² + 2n + 1 - n - 1
{ das selbe wie oben, nur anders aufgeschrieben }
=> 2 | (n+1)² - (n+1)
Es liess sich also der Induktionsschritt A(n) => A(n+1) durchführen und somit sind plötzlich alle Aussagen A(n) für jedes bleiebige natürliche n wahr.
Versuch doch mal das hier richtig gründlich gedanklich zu durchdringen. Es ist immer schön, wenn man auch wirklich genau weiss was man denn da rechnet und nicht nur versucht Schemata zu erkennen und diese auf die Aufgabe anwendet.
Bei weiteren Fragen darfst Du gerne noch mal schreiben! |
Ingo
| | Veröffentlicht am Freitag, den 12. Januar, 2001 - 01:14: |
|
Hm...wozu braucht man bei so einer Aufgabe eigentlich die Induktion ?? OKay,wenn Euer Lehrer oder Prof das so vorgibt,dann muß es wohl sein,aber das ist wie mit Kanonen auf Spatzen zu schießen,denn n2-n=n(n-1) und logischerweise ist entweder n oder n-1 gerade,also durch 2 teilbar. |
IQzero
| | Veröffentlicht am Freitag, den 12. Januar, 2001 - 12:07: |
|
Hi Ingo!
Selbstverständlich ist Deine Lösung für die Aufgabe viel einfacher. Ich denke es geht aber nicht in erster Linie darum einzusehen, dass n²-n gerade ist, sondern eher darum die vollständige Induktion zu verstehen. Wenn man dazu gleich eine Aufgabe nimmt, bei der man nicht mit Kanonen auf Spatzen schiesst, dann wird es dadurch wahrscheinlich nicht einfacher die grundsätzliche Beweisidee einzusehen. |
Sabrina (Guybrush)
| | Veröffentlicht am Freitag, den 12. Januar, 2001 - 13:03: |
|
Super, vielen Dank IQzero ! Ich hab mich jetzt intensiv beschäftigt und zu Deinen Ausführungen die verschiedenen Definitionen und Sätze herausgesucht und es dann selber mal versucht und juchhu, es hat geklappt ! Danke noch mal !
Tschöö
Sabrina |
|
