Kann jemand die mathematische Induktion erklären, um eine rekursive Methode zu beweisen? Ich bin ein Studienanfänger Informatik und ich habe noch nicht Calculus genommen (ich hatte durch Trig). Ich verstehe es irgendwie, aber ich habe Probleme, wenn ich einen Induktionsbeweis für eine rekursive Methode schreiben soll.
Hier ist eine Erklärung mit Beispiel:
Nehmen wir an, Sie haben die folgende Formel, die Sie beweisen möchten:
%Vor% Diese Formel bietet eine geschlossene Form für die Summe aller Ganzzahlen zwischen 1 und n .
Wir beginnen mit dem Beweis der Formel für den einfachen Basisfall von n = 1 . In diesem Fall reduzieren sich beide Seiten der Formel auf 1 . Dies bedeutet wiederum, dass die Formel für n = 1 gilt.
Als nächstes beweisen wir, dass, wenn die Formel für einen Wert n gilt, sie für den nächsten Wert von n (oder n + 1 ) gilt. Mit anderen Worten, wenn das Folgende zutrifft:
Dann gilt auch Folgendes:
%Vor%Beginnen wir mit der ersten Seite der letzten Formel:
%Vor% Das heißt, die Summe aller ganzen Zahlen zwischen 1 und n + 1 ist gleich der Summe der ganzen Zahlen zwischen 1 und n , plus der letzte Begriff n + 1 .
Da wir diesen Beweis auf der Bedingung basieren, dass die Formel für n gilt, können wir schreiben:
Dies beendet den induktiven Beweis, aber was bedeutet das eigentlich?
n korrekt ist, ist sie für n + 1 korrekt. Von 1 und 2 können wir sagen: Wenn die Formel für n = 0 richtig ist, dann ist es richtig für 0 + 1 = 1 . Da wir den Fall von n = 0 bewiesen haben, ist der Fall von n = 1 in der Tat richtig.
Wir können diesen obigen Vorgang noch einmal wiederholen. Der Fall von n = 1 ist korrekt, dann ist der Fall von n = 2 korrekt. Diese Argumentation kann ad infinitum gehen; Die Formel ist korrekt für alle ganzzahligen Werte von n & gt; = 1.
Induktion! = Calc !!!
Ich kann N Jungs mit 10 * N Bier betrunken machen.
Base Case: 1 Typ
Ich kann einen Kerl betrunken mit 10 Bieren
bekommenInduktionsschritt, gegeben p (n) beweisen p (n + 1)
Ich kann Leute mit 10 * i Bier betrinken, wenn ich einen anderen Mann hinzufüge, kann ich ihn mit 10 weiteren Bieren betrunken machen. Daher kann ich i + 1 Jungs mit 10 * (i + 1) Bier betrunken machen.
p (1) - & gt; p (i + 1) - & gt; p (i + 2) ... p (inf)
Diskrete Mathematik ist einfach!
Zuerst benötigen Sie einen Basisfall. Dann brauchen Sie einen induktiven Schritt, der für einen Schritt n gilt. In Ihrem induktiven Schritt benötigen Sie eine induktive Hypothese. Diese Hypothese ist die Annahme, die Sie gemacht haben müssen. Schließlich, verwenden Sie diese Annahme, um Schritt n + 1 zu beweisen