Aufgabe:
Ich versuche mittels starker Induktion zu beweisen, dass die rekursiv definierte Funktion
f(n) = 1 ,falls n=1
f(n) = 1 + f(⌊\( \frac{n}{2} \)⌋) ,sonst
die Anzahl der Ziffern der Binärdarstellung von n berechnet, wobei n∈ℕ.
Problem/Ansatz:
I.B. f(1)=1. Da 110=12 stimmt die Aussage.
I.H. Angenommen, f(k) entspricht der Anzahl der Ziffern der Binärdarstellung für alle k≤n.
I.S.
⊗ 1.Fall: Falls n+1 eine Zweierpotenz ist, dann hat n+1 die Form 2m für ein m∈ℕ. Die Binärdarstellung von n+1 hat m+1 Ziffern. Und f(n+1) = f(2m) = 1 + m, nach I.H.
⊗ 2.Fall: Falls n+1 keine Zweierpotenz ist, dann haben die Binärdarstellungen von n und n+1 die selbe Anzahl an Ziffern. Das bedeutet, dass f(n) und f(n+1) dieselben Werte liefern. Also f(n+1) = 1+f(⌊\( \frac{n+1}{2} \)⌋) = 1+f(⌊\( \frac{n}{2} \)⌋) und nach I.H gilt dann, dass dies die richtige Anzahl an Ziffern in Binärdarstellung ergibt. ▢
Ich bin mir beim Induktionsschritt leider sehr unsicher. Könnte mir jemand helfen, dies etwas genauer und mathematisch korrekter aufzuschreiben?