0 Daumen
49 Aufrufe

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?

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community