Wie wendet man Induktion bei einer Rekurrenzgleichung an?

Question

Beweisen Sie durch Induktion die Lösung BN = ⌈log N ⌉ +1 für die Rekurrenzgleichung.
BN = B _⌈N2⌉ + 1 für N ≥ 2
B1 = 1.

 

Wie, was, wo? Wie kann man denn bei so einer Aufgabe Induktion anwenden?

Comments

Ist das "N2" zutreffend? Also, N sollte immer mit Rechenoperationen versehen sein. N + 1, N/2, 2*N etc.

Answer 1

Die Induktionsannahme ist, dass die Lösung BN = ⌈log N⌉ + 1 für alle N > 1 korrekt ist. Wir werden dies nun für N + 1 beweisen.

Basisfall: N = 1, B1 = 1. Das ist korrekt.

Induktionsschritt: Angenommen, die Aussage ist für N = k korrekt. Das heißt, Bk = ⌈log k⌉ + 1. Wir müssen nun zeigen, dass die Aussage auch für N = k + 1 gilt.

BN+1 = B ⌈(k+1)^2⌉ + 1
= B(k+1)^2 +1
= B(k^2 + 2k + 1) + 1 (k^2 = ⌈k^2⌉ für alle k > 1)
= Bk + 2Bk + B1 + 1 (durch Annahme)
= ⌈log k⌉ + 1 + 2(⌈log k⌉ + 1) + 1 (durch Annahme)
= ⌈log k⌉ + 1 + 2⌈log k⌉ + 2 + 1
= ⌈log k⌉ + 1 + ⌈2log k⌉ + 3
= ⌈log(k+1)⌉ + 1

Da die Induktionsannahme für N = k und der Induktionsschritt für N = k + 1 beide korrekt sind, folgt daraus, dass die Aussage BN = ⌈log N⌉ + 1 für alle N > 1 richtig ist.