Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Vollständige Induktion
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Vollständige Induktion
 
Autor Nachricht
Gast







BeitragVerfasst am: 19 Okt 2004 - 10:38:43    Titel: Vollständige Induktion

Ich setzte mich gearde mit dem Kapitel Vollständige Induktion auseinander, doch ohne ein konkretes Beispiel ist es oft schwer nachvollziehbar.

Könnte mir bitte jamand kurz anhand dieses Beispieles erklären, wie es zu lösen wäre.

Zeigen Sie das für alle n aus N gilt: 64|9 hoch n - 8n - 1


Mfg Herbert
xaggi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.03.2004
Beiträge: 1190

BeitragVerfasst am: 19 Okt 2004 - 11:32:20    Titel:

1. Induktionsanfang:

Die Behauptung ist für n=0 wahr, denn

9^0 - 8*0 - 1 = 0

ist durch 64 ohne Rest teilbar (0 * 64 = 0)


2. Induktionsschritt:

Die Behauptung sei für an wahr, es ist also
an = 9^n - 8n - 1
ohne Rest durch 64 Teilbar.

Man kann an dann auch als k-faches von 64 schreiben, wobei k eine natürliche Zahl ist:
an = k * 64

zu zeigen: Die Behauptung ist auch für a(n+1) wahr.

a(n+1) = 9^(n+1) - 8 * (n+1) - 1 = 9^n * 9 - 8n - 8 - 1

= 9^n - 8n - 1 + 8 * 9^n - 8

= an + 8 * (9^n - 1)

= an + 8 * (9^n - 1 - 8n + 8n)

= an + 8 * (an + 8n)

= an + 8 an + 64 n = 9 an + 64 n

mit an = k * 64:

= 64 * (9k + n)

da k und n natürliche Zahlen sind, ist also a(n+1) das 64-fache einer Natürlichen Zahl (9k+n), und damit ohne Rest durch 64 teilbar.

q.e.d.
Gast







BeitragVerfasst am: 19 Okt 2004 - 11:35:40    Titel:

Danke für deine rasche und ausfürliche Hilfe.
xaggi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.03.2004
Beiträge: 1190

BeitragVerfasst am: 19 Okt 2004 - 14:21:54    Titel:

Zitat:
Ich habe im unteren Beitrag ein Beispiel über die Vollständige Induktion gelesen, doch leider ist mir die Vorgehensweise nicht klar.

Könnte mir vielleicht jemand die einzelnen Schritte näher erläutern?
Tappe etwas im Dunklen herum.

Hier ist nocheinmal das Beispiel: 64 | 9 hoch n - 8n - 1

Danke für die Hilfe



Also mal ganz langsam und zum Mitschreiben ;-).

Das Beweisverfahren der vollständigen Induktion ist ein Verfahren, bei dem es darum geht, zu zeigen, dass eine bestimmte Aussage für alle Natürlichen Zahlen richtig ist.
Das passiert in zwei Schritten:

1. Der Induktionsanfang:
Man zeigt, dass die Aussage für einen Anfangswert (üblicherweise 0 oder 1) richtig ist.

2. Der Induktionsschritt:
Man zeigt, dass, wenn die Aussage für eine beliebige natürliche Zahl n gilt, sie auch immer für die jeweils nächste Zahl n+1 gelten muss.

Damit hat man die Aussage für ALLE natürlichen Zahlen bewiesen.


Das Beweisverfahren der vollständigen Induktion ist relativ eng verwandt mit Zahlenfolgen, denn im Grunde lässt sich jedes Problem, dass ausschließlich natürliche Zahlen betrifft, in irgendeiner Form als Folge ausdrücken.

Im obigen Beispiel kann man z.B. die Folge (an) mit an = 9^n - 8n - 1 aufstellen.
Das Problem lässt sich dann auch formulieren als:
"Zeige, dass alle Folgenglieder der Folge (an) ganzzahlige Vielfache von 64 sind".

Man zeigt also zunächst, dass die für a0 = 9^0 - 8*0 - 1 = 0 der Fall ist.
Da 0 eigentlich keine natürliche Zahl ist, könnte man es im Grunde auch für a1 = 9^1 - 8*1 - 1 = 0 zeigen, das macht hier aber keinen Unterschied und hängt im allgemeinen von der Fragestellung ab. Wenn möglich, ist aber der Startwert 0 die sicherere Variante, da damit die 1 eingeschlossen ist.
0 ist natürlich ein Vielfaches von 64 (nämlich das Nullfache).
Die Behauptung ist also für n=0 (oder n=1) wahr.

Im zweiten Schritt gilt es zu zeigen, dass die Behauptung für n+1 wahr ist, WENN sie für n wahr ist. Und genau dieses WENN kann man sich zunutze machen. Man weiß nämlich (weil es die Annahme ist, die man vorher getroffen hat), dass an = 9^n - 8*n - 1 ein Vielfaches von 64 ist.

Wenn man es also schafft, a(n+1) = 9^(n+1) - 8*(n+1) - 1 so unzuschreiben, dass man eine Summe aus an's und anderen Vielfachen von 64 erhält, dann ist auch a(n+1) ein Vielfaches von 64, denn eine Summe von Vielfachen einer Zahl ist immer ein Vielfaches dieser Zahl (i*n + j*n = k*n, mit i,j,k,n € |N).

Ich hoffe, ich hab mich jetzt nicht zu Fachidiotisch ausgedrückt, aber anders wärs wohl falsch oder zumindest ungenau geworden. Nachfragen ist natürlich erlaubt.
V.L.i.1.S.
Gast






BeitragVerfasst am: 01 Nov 2004 - 15:54:41    Titel: Erlaubte Nachfrage...

Hallo zusammen,

durch eure Posts ist mir das Verfahren der vollständigen Induktion zum ersten Mal ein bisschen klar geworden. Die euch gegebene Fragestellung und ihre Lösung habe ich nachvollziehen können.

Nun habe ich folgende Aufgabe zu bearbeiten:

Man zeige, dass 11^(n+1) + 12^(2n-1) für alle n aus |N durch 133 teilbar ist.

Meine Lösung:

1. Induktionsanfang (bzw. -verankerung, wie auch immer):

Für n=1: 11^(1+1) + 12^(2·1-1) = 11² + 12 = 133 (wahr)


2.1 Induktionsvoraussetzung:

"11^(n+1) + 12^(2n-1) für alle n aus |N durch 133 teilbar" gelte

2.2

Für n+1 ergibt sich: 11^((n+1)+1) + 12^(2(n+1)-1)

Substituiere n + 1 aus |N = k aus |N

-> = 11^(k+1) + 12^(2k-1) (wahr, da k aus |N ist und die Aussage für alle natürlichen Zahlen gilt)

------------

Ist dies so stimmig? Ist die Induktivität der natürlichen Zahlen in sich hinreichend, damit der Schritt "Substituiere ..." erlaubt ist? Oder mache ichs mir zu einfach?

Beste Grüße,
Verzweifelter Lehramtsstudent im 1. Semester
Wink
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 01 Nov 2004 - 16:04:08    Titel:

Hier sind gleich zwei typische Fehler:

2.1. ist Falsch, denn da nimmst Du die Gültigkeit der zu zeigenden Aussage an -> Kreisschluß

2.2. Substitution ist hier rein syntaktisch und verändert die Semantik nicht. Anders gesagt: Da steht immer noch das, was vorher stand.

Ich glaube "Induktivität" ist was aus der Physik... Lies den Beitrag oben genauer durch.
V.L.i.1.S.
Gast






BeitragVerfasst am: 01 Nov 2004 - 18:53:09    Titel: Nächster Versuch...

So, dann werd ichs noch mal wagen. Danke schon mal vorweg für eure Hilfe bzw. Geduld Smile

1. Induktionsanfang bleibt gleich

2.1 Induktionsvoraussetzung:

"11^(n+1) + 12^(2n-1) für EIN n aus |N durch 133 teilbar" gelte

2.2

Für n+1 ergibt sich: 11^((n+1)+1) + 12^(2(n+1)-1) = 11·11^(n+1) + 12²·12^(2n-1) = 11·11^(n+1) + 144·12^(2n-1)

Und hier weiß ich nicht weiter, wahrscheinlich fehlt mir einfach die Idee zum nächsten Rechenschritt...?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 01 Nov 2004 - 19:26:06    Titel:

Der Weg ist nun ok. Ich weiss auch selber nicht, wie es weiter geht. Bin zu faul um das zu rechnen. Ist bestimmt irgend so ein +1-1 Trick.
xaggi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.03.2004
Beiträge: 1190

BeitragVerfasst am: 01 Nov 2004 - 19:36:38    Titel:

Der Rest ist doch einfach:

12^2 * 12^(2n-1) = 12^(2 + (2n-1)) = 12^(2n + 2 -1) = 12^(2(n+1)-1)

und

11 * 11^(n+1) = 11^(1 + (n+1)) = 11^((n+1)+1)
Josch
Gast






BeitragVerfasst am: 07 Nov 2004 - 01:01:28    Titel:

hehe, ja ich studiere auch in essen!!!
wer bist du??wie siehst aus??welche übung??
dvon dem neuen übungszettel check ich gar nichts!!!

ps.: 144 - 11 is gut...bis i da ma druff gekommen bin hat gedauert!!
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Vollständige Induktion
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum