Vollständige Induktion

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Vollständige Induktion
Hi :slight_smile:
die Übungen zur vollständigen Induktion haben bei mir ganz gut geklappt und im Rahmen meiner Klausurvorbereitung wollte ich nochmal ganz kurz reinschauen um sicher zu gehen. Einige Beispielaufgaben die ich dazu gemacht habe liefen super, aber bei einer hängt es zurzeit. Die Aufgabe ist aus dem 4. Übungsblatt vom 19.11.2018.
Folgende Funktion soll induktiv bewiesen werden:

public static long magic(long n) {
    if (n > 2) {
	return 9 * magic(n-2) - 16;
    } else {
	return 2 * n + 1;
    }
}

und zwar hinsichtlich:
https://imgur.com/a/KV0jKXn
Ich versuche das jetzt schon sehr lange aber ich krieg es einfach nicht hin…
Ich habe 2 Anfänge (für n=0 und n=1) und 2 Vorraussetzungen (Aussage stimmt für n-1 und n-2) und mache den Schritt von n-1 auf n.
Aber ich schaffe es irgendwie nicht, den term korrekt umzuformen. ich denke ich hab irgendwo einen dummen fehler gemacht, den ich nicht finde.
Kann mir jemand helfen?
Mein bisheriger Fortschritt: https://imgur.com/a/FvMBcvg

Danke euch :slight_smile:

3

Da die Funktion von n auf n-2 geht, empfiehlt es sich, als Schrittgröße ebenfalls 2 zu benutzen.

4

n=0 sollte erstmal nicht nötig sein, da die zu beweisende Aussage nur etwas für n >= 1 fordert. Außer du hast Pech und die zu beweisende Aussage erfordert zuerst ein stärkeres Resultat und folgt dann als Korollar. (Also wenn man manchmal \forall n. P(n) beweisen möchte per Induktion, kann es nötig sein zuerst \forall n. Q(n) zu beweisen, wobei für alle n Q(n) eine stärkere Aussage als P(n) ist, d.h. \forall n. Q(n) => P(n). Somit folgt \forall n. P(n) als direktes Korollar. Meine Worte mit „kann es nötig sein“ sind nicht unbedingt formal zu verstehen, d.h. zwingend nötig i. S. d. Logik muss es nicht sein, kann aber einfacher sein.)

2 Voraussetzungen zu nehmen ist legitim, aber dann machst du den Schritt eigentlich von {P(n-2), P(n-1)} auf P(n).

(In der tat kannst du die Aussage auch für alle m < n annehmen, d.h. von {P(1), P(2), …, P(n-1)} auf P(n) schließen.

Als du die Summe von i=0 bis i=n-4 aufgesplittet hast zu einer Summe von i=0 bis i=n-2 und zwei Termen, hast du die Vorzeichen falsch herum gesetzt.

Aber dann beweist man nur etwas für die geraden (oder ungeraden) natürlichen Zahlen. Die Aussage \forall n >= 1. P(n) gilt jedoch für alle natürlichen Zahlen >= 1. D.h. der Beweis wäre lückenhaft für das, was zu zeigen wäre.

5

[quote=Marcel[Inf]]
Als du die Summe von i=0 bis i=n-4 aufgesplittet hast zu einer Summe von i=0 bis i=n-2 und zwei Termen, hast du die Vorzeichen falsch herum gesetzt.
[/quote]
Die Summe bis n-2 ist doch größer als die Summe bis n-4, weswegen man die überschüssigen Summanden abziehen muss. Und nach dem ausmultiplizieren wird das Vorzeichen gewechselt, weil - * - = + oder nicht? Mit einigen Testwerten kommt bei mir vor und nach dem splitten auch das gleiche heraus.

edit: huiuiui die forensoftware stellt zitate von leuten mit eckigen klammern im username nicht richtig dar :smiley:

6

Du hast recht, mein Fehler. Dann ist vielleicht der weitere Verlauf falsch, den hatte ich mir dann nicht mehr angesehen.

7

Hast du vielleicht eine Idee? weil ich komm echt nicht drauf…

8

Habe einmal die Rechnung als Bild angehängt. Du hast dich nur einmal mit den Indizes in der Summe vertan.
BTW: Brauche immer noch jemanden fürs GTI Praktikum - ich habe noch nicht alle Vorbereitungsaufgaben raus…

Attachment:
WhatsApp Image 2020-02-29 at 14.22.43.jpeg: https://fsi.cs.fau.de/unb-attachments/post_163595/WhatsApp Image 2020-02-29 at 14.22.43.jpeg

9

Danke :))
war mir echt eine große hilfe