Für jedes n ∈ N+ gilt f(n) ≤ log2(n)?

Wir sollen die Aussage in GBI mit vollständiger Induktionen beweisen. Induktionsanfang und Induktionsvorraussetzung habe ich schon. Ich verstehe jedoch nicht wie man das ganze jetzt mit n-1 auf n beweisen kann.

Comments

[nobytree2]

Wie wird f(n) definiert?

[LeonFtb]

Oh ja völlig vergessen! Sei f : N+ → N0 eine Funktion mit f(1) = 0 und f(n) = f(⌊n/2⌋)+1

Answer 1

[nobytree2]

Eine Idee vor, die mir jetzt erst kam:

Wir gehen nicht auf n+1, sondern auf 2n bzw. nicht n-1 zu n, sondern n/2 zu n.

Dann haben wir

$\log_2\left(2n\right)\ge f\left(2n\right)=f\left(\lfloor\frac{2n}{2}\rfloor\right)+1=f\left(n\right)+1$ wahr weil

$\log_2\left(2n\right)=\log_2\left(n\right)+\log_2\left(2\right)=\log_2\left(n\right)+1$

Und jetzt die Spanne von n+1 bis 2n

$Sei\ m\in\mathbb{N}\cap\left\{n+1,...,2n-1\right\}:\log_2\left(m\right)=f\left(\lfloor\frac{m}{2}\rfloor\right)+1=f\left(n-1\right)+1$ ebenfalls wahr, da

$f\left(n-1\right)+1\le f\left(n\right)$

qed

Vorige Antwort:

Es hilft ein bisschen Analyse! f ergibt also eine Folge mit

f(1) = 0, f(2) = 1, f(3) = 1, f(4) = 2, f(5) = 2, f(6) = 2, f(7) = 2, f(8) = 3

Wie baut ich diese Folge auf? Am Anfang steht die 0, dann kommt zweimal die 1, dann viermal die 2, achtmal die 3, 16mal die 4 etc. Damit lässt sich die Funktion umschreiben zu

$f\left(n\right)=\lfloor\log_2\left(n\right)\rfloor$
Das wollen wir ausnutzen, wobei ich nicht von n-1, sondern von n ausgehen, ist hier einfacher, der Sache nach dasselbe. Sei obige Gleichung (aus der dann die zu beweisende Aussage unmittelbar folgt) für n bewiesen.

Wir untersuchen n+1. Es gibt zwei Möglichkeiten.

$Möglichkeit\ 1:\ \lfloor\frac{n+1}{2}\rfloor=\lfloor\frac{n}{2}\rfloor$

Dann ergibt sich aus dem Beweis für n, dass die Ausgangsfrage (die jetzt hier direkt bewiesen wird) auch für n+1 gilt, da log(n+1) > log(n) und damit bleibt die Ungleichheit beibehalten (Transitivität der partiellen Ordnung).

Jetzt der andere Fall:

$Möglichkeit\ 2:\ \lfloor\frac{n+1}{2}\rfloor=\lfloor\frac{n}{2}\rfloor+1$

Das ist nur bei ungeraden Zahlen der Fall. In diesem Fall wird der Index um 1 erhöht. Bei jeder zweiten Zahl wird damit der Index um 1 erhöht. Im Ergebnis greifen f(1), f(2) auf f(0) zu, f(3), f(4) auf f(1), dann f(5), f(6) auf f(2) = f(1), wodurch sich obiges Muster ergibt. Das ist aber noch nicht mathematisch ausgedrückt.

Es gilt also (wir hätten es gleich so schreiben können), weil

$\forall m\in\mathbb{Z}:\lfloor\ \frac{2m+1}{2}\ \rfloor\ =\ \lfloor\ m+\frac{1}{2}\rfloor=\lfloor m\rfloor=\lfloor\ \frac{2m}{m}\rfloor$ damit:

$\forall m\in\mathbb{N}^+:\ f\left(2m+1\right)=f\left(2m\right)=f\left(m\right)+1$ Mit jeder Verdoppelung von m erhalten erhalten f und f für den Nachfolger den Wert von f für die Hälfte.

Jetzt sind wir fast fertig. Aus obiger Gleichung folgt, dass mit jeder Verdoppelung von m die Funktion den Wert von f annimmt plus 1 sowie dass die Erhöhung von m auf eine ungerade Zahl den Wert von f nicht ändert. Umgekehrt bedeutet dies,

$\forall m\in\mathbb{N}^+:\ f\left(m\right)=f\left(2m\right)-1=f\left(2m+1\right)-1$

Damit wird die Funktion f beschrieben. Für Logarithmus 2 gilt jedoch

$\log_2\left(m\right)=\log_2\left(\frac{2m}{2}\right)=\log_2\left(2m\right)+\log_2\left(\frac{1}{2}\right)=\log_2\left(2m\right)-1$

$jedoch\ auch\ \forall m\in\mathbb{R}:\log_2\left(2m+1\right)>\log_{2\ }\left(2m\right)$

Wenn m gerade ist, dann steigt die Funktion f also maximal so schnell wie log2. Da wir in der Induktion bewiesen haben, dass f(n) <= log2(n), gilt, dass für gerade m f(n) mangels schnellerem Anstieg nicht höher sein kann als log2(n).

Ist m jedoch ungerade, entspricht der Wert von f dem Wert von f für m-1, die Steigung ist also geringer als bei log2(n). Da wir in der Induktion bewiesen haben, dass f(n) <= log2(n), gilt, dass für auch für ungerade m f(n) mangels schnellerem Anstieg nicht höher sein kann als log2(n).

Der Beweis gefällt mir allerdings überhaupt nicht, er läuft über eine Art Ableitung von diskreten Funktionen und nutzt die Induktion nur unzureichend. Mir fällt aber gerade nichts besseres ein.

Comments

[nobytree2]

Irgendwie wollte ich mit der Induktion beweisen, dass f(n) nur dann um 1 nach oben springt, wenn es ein m gibt, für das gilt 2^m = n. Von diesem Weg bin ich irgendwie hier abgekommen ...

[nobytree2]

@nobytree2

habs jetzt doch geschafft und ganz oben eingefügt :-)

[Nutzer410]

@nobytree2

Vielen Dank,
mir bleibt hier nur noch die Frage, woher wir Wissen, dass f(n−1)+1≤f(n)?

[nobytree2]

@Nutzer410

Wir betrachten f(n−1)+1≤f(n) ja ausschließlich für den Fall, dass m/2 abgerundet werden muss und - das war hier tatsächlich zu kurz - n darstellbar ist als 2^m mit m natürliche Zahl, denn in der Induktion wollen wir ja nicht n+1, sondern 2*n voranschreiten, was dazu führt, dass der erste Fall immer ein 2^m-Fall ist.

Wenn n = 2^m haben wir f(n) = log2(n), das ist einfach zu beweisen, f(2n) = f(n) + 1, mit jeder Verdoppelung von n kommt 1 hinzu, dass ist log2(2n) = log2(n) + 1. Ansonsten wegen der Abrundung zwingend nicht (der Beweis steht etwas überausführlich in der älteren, längeren Antwort, das kann man aber gut verkürzen). Im Prinzip muss es auch deswegen ungleich sein, da log2(z ungleich 2^m) nicht in N, sondern nur in R ist. Aber f(n) ist immer in N und f(n) niemals größer log2(n), siehe dazu den Beweis mit der Majoranten (den man wie gesagt gut verkürzen kann, bei f(n) wird ja abgerundet und damit nach weiter hinten referenziert)

Sei nun m so gewählt, dass 2^m der nächst größere Wert oberhalb von n ist. Da wegen n < 2^m, gilt f(n) < f(2^m), siehe oben. Der Abstand aber ist mindestens 1, da f nur natürliche Zahlen zurückgibt.