Induktionsnachweis

JerryB.

Neues Mitglied
Hallo zusammen,
kann mir vllt einer von euch erklären, wie der Induktionsnachweis mittels vollständiger Induktion bei einer Java Methode funktioniert?
Einen Beispiel für die Java Methode könnt ihr selber aussuchen.:D
Vielen Dank im Voraus.
JerryB.
 

MoxxiManagarm

Top Contributor
Beispiel: Die Summe aller natürlichen Zahlen von 1 bis n ist n(n+1)/2.

Dann hast du sicherlich folgende rekursive Java Methode gegeben:
Java:
public static int sum(int n) {
     if(n == 1) return 1; // Abbruchbedingung
     return n + sum(n - 1);
}

Was auf Papier einfach soviel heißt wie f(n) = n +f(n-1) bzw. f(1) = 1

Nun zeigst du, dass beide Formeln für ein oder mehrere Ankerpunkte wahr ist (Induktionsanfang), indem links und rechts übereinstimmen.

Links: f(1) = 1
Rechts: f(1) = 1(1+1)/2 = 1*2/2 = 1
OK

Links: f(2) = 2 + f(1) = 2 + 1 = 3
Rechts: f(2) = 2(2+1)/2 = 2*3/2 = 3
OK

Daraufhin zeigst du, dass die Aussage auch für n+1 wahr ist.
Links: f(n+1) = (n+1) + f(n)
Rechts: f(n+1) = (n+1)((n+1)+1)/2 = (n+1)(n+2)/2

Du kannst Links für f(n) die Formel einsetzen und erhälst
Link: f(n+1) = (n+1) + n(n+1)/2

Du willst nun also zeigen links = rechts
(n+1)(n+2)/2 = (n+1) + n(n+1)/2 // wir erweitern (n+1) mit 2 um alles auf einen Strich zu schreiben
(n+1)(n+2)/2 = (2(n+1) + n(n+1))/2 // die 2 kannst du auf beiden Seiten streichen
(n+1)(n+2) = 2(n+1) + n(n+1) // das kannst du einfach auflösen, also ausmultiplizieren
n^2 + 2n + n + 2 = 2n + 2 + n^2 + n // umsortieren und zusammenfassen
n^2 + 3n + 2 = n^2 + 3n + 2 // was zu beweisen war
 

Neue Themen


Oben