wir haben folgende Aufgabe: (siehe Bild Induktion)
Prinzipiell ist mir klar was vollständige Induktion ist. In Mathe hatten wir das. Da sah dies jedoch etwas anders aus.
Was mir hier nicht klar ist, ist was eig die Annahme ist?
In Mathe bsp stande da: Summenzeichen(i=1 bis n) 2i = n(n+1)
Und bei dem Blatt ist mir schon mal gar nicht klar welche Annahme ich herausnehme.
Die obige Form fehlt mir.
Kann mir jemand einen Tipp geben?
Info: Unter dem Summenzeichen bei diesem Blatt steht i=0, das erkennt man leider nicht mehr wurde abgeschnitten.
Die Behauptung ist das, was Du beweisen sollst. Das zeigst Du in dem Fall für n=1 und nimmst es im Folgenden als gegeben an. Unter dieser Annahme zeigst Du, dass die Behauptung auch für n+1 gilt.
Du hast zwei Dinge: einmal die rekursive Definition von der Funktion magic, und einmal den geschlossenen Ausdruck mit der Summenformel. Du sollst zeigen, dass über beide "Berechnungsmethoden" stets das gleiche heraus kommt.
Du brauchst im Übrigen zwei Induktionsanker, n=1 und n=2. Und anschließend schaust du dir einfach magic(n+2) mal genauer an.
Du hast zwei Dinge: einmal die rekursive Definition von der Funktion magic, und einmal den geschlossenen Ausdruck mit der Summenformel. Du sollst zeigen, dass über beide "Berechnungsmethoden" stets das gleiche heraus kommt.
Du brauchst im Übrigen zwei Induktionsanker, n=1 und n=2. Und anschließend schaust du dir einfach magic(n+2) mal genauer an.
Der Schluss von der Gültigkeit der Aussage für festes n auf die Gültigkeit der Aussage für n+1 wird dir nicht direkt gelingen, wohl aber der Schluss auf die Gültigkeit der Aussage für n+2 ... das ist ein 3-Zeiler.
Zusammen mit der explizit durchgerechneten Gültigkeit der Aussage für n=1 und n=2 hast du dann aber alle natürlichen Zahlen abgedeckt und bewiesen, dass die Aussage allgemein gültig ist.
Das liegt einfach daran, wie magic(n) definiert ist...
Genauer gesagt schließt man hier eigentlich aus der Gültigkeit der Aussage für zwei aufeinanderfoglende Zahlen n und n+1, auf die Gültigkeit der Aussage für n+2 (ohne dass man bei der Beweisführung die Gültigkeit für n+1 braucht)
Genauer gesagt schließt man hier eigentlich aus der Gültigkeit der Aussage für zwei aufeinanderfoglende Zahlen n und n+1, auf die Gültigkeit der Aussage für n+2 (ohne dass man bei der Beweisführung die Gültigkeit für n+1 braucht)
Wie formuliere ich jetzt meine Frage, ohne größeren Einfluss auf den TO zu nehmen? Hm... Verstehe ich Dich richtig, dass Du strikt zwischen vollständiger und starker Induktion unterscheidest?
Man kann das eine natürlich als Variante des anderen betrachten. Und es ist natürlich auch gehopst wie gesprungen, wo man anfängt zu zählen.. Man muss nur bei der Beweisführung auspassen, dass man sauber und lückenlos argumentiert.
Ich hoffe, dass das jetzt nicht zu sehr an deiner Frage vorbei ging
Übrigens ist der Beweis hier nicht ganz so trivial wie vielleicht manch anderer. Daher hier ein Tipp von mir:
Man wird im Laufe des Beweises vermutlich die Summe [k:=0..n]∑3^k auf eine Seite bringen müssen. Diese hat dann einen Multiplikator p.
Mit etwas Umformung von p kann man die Teleskopregel anwenden um das Summenzeichen loszuwerden.
Teleskopregel: (1-z)[k:=0..n]∑z^k = 1 - z^(n+1), also für diesen Fall -2[k:=0..n]∑3^k = 1 - 3^(n+1)
Übrigens ist der Beweis hier nicht ganz so trivial wie vielleicht manch anderer. Daher hier ein Tipp von mir:
Man wird im Laufe des Beweises vermutlich die Summe [k:=0..n]∑3^k auf eine Seite bringen müssen. Diese hat dann einen Multiplikator p.
Mit etwas Umformung von p kann man die Teleskopregel anwenden um das Summenzeichen loszuwerden.
Teleskopregel: (1-z)[k:=0..n]∑z^k = 1 - z^(n+1), also für diesen Fall -2[k:=0..n]∑3^k = 1 - 3^(n+1)
Der einzige "Trick", den man braucht, ist es eigentlich nur zu wissen, dass 16 die Summe aus 4 und 12 ist.... und damit hab ich jetzt noch mehr von der Lösung verraten, aber den Beitrag kann man ja so nicht stehen lassen
