vollständige Induktion, Java

[O2016]

Hallo,

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.

 

[mihe7]

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.

 

[O2016]

ok. n=1 soweit klar. aber
wie beweise ich n+1. Ich kann doch nicht n+1 in magic(n) einsetzen oder?

 

[stg]

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.

 

[mihe7]

Und anschließend schaust du dir einfach magic(n+2) mal genauer an.

Oops, da steht ja n-2.

 

[hatutonaok27ebox]

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.

warum sagst du hier n=1 und n=2?
n=1 kann ich vtl verstehen, aber warum wäre es irgendeiner Wert n>3? z.B n=3 einsetzen


ist es ja richtig wenn man n=3 für die 1. lineare Rekursion einsetzt? und n=1 für die 2. Rekursion?

bin etwa verwirt,
bei induktionsschritt sollte man n+1 oder n-1 einsetzen?

 

[stg]

aber warum wäre es irgendeiner Wert n>3? z.B n=3 einsetzen

...nochmal auf deutsch, bitte.

bin etwa verwirt,
bei induktionsschritt sollte man n+1 oder n-1 einsetzen?

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.

 

[mihe7]

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

Warum nicht?

 

[stg]

Warum nicht?

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)

 

[mihe7]

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?

 

[stg]

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

 

[mihe7]

Ich hoffe, dass das jetzt nicht zu sehr an deiner Frage vorbei ging

Denke nicht Danke.

 

[MoxxiManagarm]

Ü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)

 

[stg]

Ü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