Rekursive Funktion mittels starker Induktion beweisen

Question

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 1₁₀=1₂ 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 2^m für ein m∈ℕ. Die Binärdarstellung von n+1 hat m+1 Ziffern. Und f(n+1) = f(2^m) = 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?