Vollständige Induktion < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich soll beweisen, dass [mm] log^{k}(n)\in [/mm] O(n) für [mm] k\in \IN [/mm] gilt.
Mein Ansatz:
Es gilt: [mm] f\in [/mm] O(g), wenn der limsup von [mm] \bruch{f(n)}{g(n)} [/mm] für [mm] n\to\infty [/mm] endlich ist.
Vollständige Induktion:
1) k=1
[mm] \limes_{n\rightarrow\infty} \bruch{log^{1}(n)}{n} \overbrace{=}^{L'Hospital} \limes_{n\rightarrow\infty} \bruch{\bruch{1}{n}}{1} [/mm] = [mm] \limes_{n\rightarrow\infty} \bruch{1}{n} \Rightarrow [/mm] 0
2) k = k+1
[mm] \limes_{n\rightarrow\infty} \bruch{log^{(k+1)}(n)}{n} \overbrace{=}^{L'Hospital} \limes_{n\rightarrow\infty} \bruch{\bruch{(k+1)*log^{k}(n)}{n}}{1} \overbrace{=}^{L'Hospital} \limes_{n\rightarrow\infty} \bruch{\bruch{(k+1)(k)*log^{(k-1)} (n)}{n}}{1} [/mm] = [mm] \limes_{n\rightarrow\infty} \bruch{(k+1)(k)*log^{(k-1)} (n)}{n}\overbrace{=}^{L'Hospital} \limes_{n\rightarrow\infty} \bruch{\bruch{(k^{2}-1)(k)*log^{(k-2)} (n)}{n}}{1} [/mm] = [mm] \limes_{n\rightarrow\infty} \bruch{(k^{2}-1)(k)*log^{(k-2)} (n)}{n} \overbrace{=}^{L'Hospital} [/mm] ... Hier weiß ich nicht wie ich weiter machen soll, weil mit ableiten komme ich hier anscheinend nicht ans Ziel.
Habt ihr paar Tipps für mich?
Vielen Dank im Voraus.
LG Bubbles
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Do 25.06.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
