Vollständige Induktion

[Cheatah]

Hi,

Diplomaten begrüßen sich beim Neujahrestreffen, jeder begrüßt jeden, wie oft werden die Hände geschüttelt bei n Diplomaten ?
Ähnliches Problem...

ja, ein typisches Standardproblem :-)

Die vollständige Induktion hat immer ein Problem, der Induktionsschritt ist immer sehr tricky.

Eigentlich nicht. Man schaut sich ein paar einfache Fälle an (sprich: die ersten paar) und überlegt sich, was von einem zum nächsten Fall eigentlich passiert ist. Das verpackt man in eine allgemeine Formel - was oft wirklich nicht schwer ist - et voilà: man hat die Differenz[1] zwischen F(n) und F(n+1).

Ich bin der Überzeugung, daß wenn man den Induktionsschritt kennt, dann findet man eine ebensogute nicht-rekursive Lösung.

Ich finde, vollständige Induktion ist eine der leichtesten Beweismethoden. Es erfordert ein wenig Zeit, das Prinzip zu verinnerlichen; danach ist es aber etwas, das man in vielen Fällen im Kopf durchexerzieren kann. Aber Meinungen sind zum Glück ebenso verschieden, wie es Denkweisen sind :-)

Cheatah

[1] Bitte nicht mit der gleichnamigen Grundrechenart verwechseln ;-)