Induktion eines aufgerundeten Logarithmus

Neue Frage »

Ninafragt Auf diesen Beitrag antworten »
Induktion eines aufgerundeten Logarithmus
Meine Frage:
Ich studiere Informatik im zweiten Semester und habe Induktion zurzeit als Thema. Als Aufgabe soll ich beweisen das f(n) Og(n) ist wobei f(n)= und g(n)= n. (Wobei die eckigen Klammern dafür stehen, dass der Logaritmus zur nächsten natürlichen Zahl aufgerundet wird.)
Als Definition der oberen Grenze hatten wir das f(n)c×g(n) ist Ich habe die beiden Graphen mal in einen Funktionsplotter eingegeben, damit ich gültige Werte für c und n kriege.


Meine Ideen:
Meine Induktionsvorraussetzung ist also :
Mein Induktionsanfang: -> 0?2 (c habe ich frei gewählt)
Als Iduktionsschritt habe ich nun n -> n+1 also:

Mein Problem ist, dass ich relativ ideenlos bin wie ich die aufrundenden Klammern los werde. Den Logaritmus kann ich umformen zu:

Aber sobald ich einen Term aus den Klammern rausziehe verändere ich doch den Sinn oder?
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

es ist .
Dementsprechend kann man hier auch zeigen:
was man per Induktion zeigen kann sofern man denn unbedingt will.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »