Beweis mittels voll. Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man beweise durch vollständie Induktion:
Die Zahl [mm] 7^{n} [/mm] -1 ist für alle n aus den natürlichen Zahlen durch 6 teilbar. |
Tja, sicherlich keine schwere Aufgabe, wenn man mit dem Verfahren der vollständigen Induktion vertraut ist. Das bin ich jedoch nicht wirklich 
Ich würde in 3 Schritten vorgehen:
1. [mm] 7^{1} [/mm] -1 = 6 ist durch 6 teilbar
2. [mm] 7^{n} [/mm] -1 ist durch 6 teilbar
3. [mm] 7^{n+1} [/mm] -1 = [mm] 7^{n} [/mm] -1 ist durch 6 teilbar
Bei Schritt 3 bin ich mir gar nicht sicher.
Ich wäre auch dankbar über Tipps, wie im allgemeinen etwas mittels vollständiger Induktion beweist.
Vielen Dank im Voraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo!
> 1. [mm]7^{1}[/mm] -1 = 6 ist durch 6 teilbar
Das ist richtig. Man nennt das Induktionsanfang oder -anker
> 2. [mm]7^{n}[/mm] -1 ist durch 6 teilbar
Das ist die Annahme, von der du ausgehen kannst, daß sie wahr ist.
> 3. [mm]7^{n+1}[/mm] -1 = [mm]7^{n}[/mm] -1 ist durch 6 teilbar
Das passt nicht, denn die Gleichung ist nicht erfüllt.
Generell versucht man hier meistens, den neuen "(n+1)"-Term irgendwie auf den alten "n"-Term zurückzuführen.
Hier ginge das so:
[mm] 7^{n+1}-1=7*7^{n}-1
[/mm]
Jetzt brauchst du eine zündende Idee. Benutze rechts mal 7*x=x+x+x+x+x+x+x=6x+x. Kannst du nun sehen, daß der rechte Term, und folglich auch der linke, durch 6 teilbar ist?
Es gibt aber auch andere Fälle, wie genau man diesen Induktionsschluß macht, hängt auch sehr von der Aufgabe ab. Bei Folgen und Reihen schrebt man meist auf die eine Seite den (n+1)-Term, und auf den anderen den n-Term, der entsprechend der Reihe noch weitergerechnet wird.
Die Summenformel ist ja [mm] $\sum_1^n i=\frac{n(n-1)}{2}$
[/mm]
Hier würde man den n+1-Term hinschreiben:
[mm] \frac{(n+1)((n+1)-1)}{2}
[/mm]
[mm] \frac{(n+1)n}{2}
[/mm]
und auf der anderen Seite den n-Term, auf den ja noch n+1 draufaddiert werden muß:
[mm] \frac{(n+1)n}{2}=\frac{n(n-1)}{2}+(n+1)
[/mm]
Dann würde man versuchen zu zeigen, daß diese Gleichung erfüllt ist.
Im ersten Fall hat man zwar auch den n+1 und n-Term da stehen, aber daß die Gleichung so stimmt, ist ziemlich trivial, und bringt einem eigentlich auch nix bezüglich der Teilbarkeit duch 6. Im zweiten muß man tatsächlich nur beweisen, daß die Gleichung erfüllt ist.
Letztendlich kann es auch noch andere Methoden geben, aber diese beiden gehören zu den häufigsten.
|
|
|
| |
|
Vielen Dank für die ausführliche Antwort, jetzt ist mir einiges klarer!
Aber sehe ich es richtig, dass der Beweis schon mit
[mm] 7^{n+1}-1=7\cdot{}7^{n}-1
[/mm]
abgeschlossen ist?
Und dann noch eine Frage zu der zweiten Möglichkeit:
Wieso zeige ich mit der folgenden Gleichung, dass die Behauptung stimmt? Diese Gleichung kann ich doch gar nicht auflösen, setzte ich z.b. für n=2 ein, so erhalte ich doch unterschiedliche Werte auf beiden Seiten???
[mm] \frac{(n+1)n}{2}=\frac{n(n-1)}{2}+(n+1)
[/mm]
|
|
|
| |
|
> Vielen Dank für die ausführliche Antwort, jetzt ist mir
> einiges klarer!
>
> Aber sehe ich es richtig, dass der Beweis schon mit
>
> [mm]7^{n+1}-1=7\cdot{}7^{n}-1[/mm]
>
> abgeschlossen ist?
Hallo,
nein.
Um mich davon zu überzeugen, daß das durch 7 teilbar ist, müßtest Du Dir no etwas einfallen lassen.
Ich glaube das so nicht.
>
> Und dann noch eine Frage zu der zweiten Möglichkeit:
> Wieso zeige ich mit der folgenden Gleichung, dass die
> Behauptung stimmt? Diese Gleichung kann ich doch gar nicht
> auflösen, setzte ich z.b. für n=2 ein, so erhalte ich doch
> unterschiedliche Werte auf beiden Seiten???
Ja.
Das liegt daran, daß sich in EventHorizons Post ein Fehler eingeschlichen hat.
Die Summenformel lautet richtig: [mm] \sum_1^n i=\frac{n(n+1)}{2} [/mm] für alle [mm] n\in \IN.
[/mm]
Wenn Du jetzt einigermaßen veratanden hast, wie Induktion geht, kannst Du das ja mal zeigen:
Induktionsanfang: zeige die Beh. für n=1
Induktionsvoraussetzung: die Aussage gelte für alle n
Induktionsschluß: zeige unter der obigen Voraussetzung, daß die Aussage auch für n+1 richtig ist.
Zu zeigen ist also [mm] \sum_1^{n+1} i=\frac{(n+1)(n+2)}{2}.
[/mm]
Beweis:
[mm] \sum_1^{n+1} i=\sum_1^{n} [/mm] i +(n+1)=...
Gruß v. Angela
>
> [mm]\frac{(n+1)n}{2}=\frac{n(n-1)}{2}+(n+1)[/mm]
|
|
|
| |
|
Hallo,
Wenn du das Prinzip der voll. Induktion verstanden hast, dann sollte auch dieses Beispiel kein großes Problem werden :)
Werde versuchen es in die einzelne Schritte zu teilen und kurz erklären. Genauere Erklärung findest du hier im Forum bei anderen Induktion oder im Wikipedia.
Also zum Beispiel:
Gegeben: [mm] 7^{n} [/mm] - 1 Soll durch 6 teilbar sein.
1. Induktionsanfang (Überprüfung ob die Aussage stimmt):
[mm] \green{7^{1} - 1 = 6} [/mm] Wahre Aussage
2. Was ist denn unsere Induktionsbehauptung ? (Was wollen wir prüfen)
--> Ob es auch für (n + 1) gilt
Unsere Behauptung ist somit: [mm] \red{7^{n+1} - 1}
[/mm]
Aus P(n) soll P(n+1) folgen:
[mm] 7^{n} [/mm] - 1 [mm] \Rightarrow 7^{n+1} [/mm] - 1
Nach dem Prinzip folgt der
3. Induktionschritt:
[mm] \blue{(7^{n} - 1) + (7^{n+1} - 1) =}
[/mm]
--> Klammern auflösen und zusammenfassen und [mm] 7^{n} [/mm] herausheben
= [mm] 7^{n} [/mm] + [mm] 7*7^{n} [/mm] -2 = [mm] \blue{8*7^{n} - 2}
[/mm]
Das war es auch schon.
Ist mein Ansatz und der Induktionsschluss überhaupt richtig? Kann mir ein Experte die Richtigkeit bestätigen?
Grüße
Delta
|
|
|
|
