Logarithmus Summe abschätzen < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich möchte [mm] \summe_{i=2}^{n} \left\lfloor log_{i}(n)\right\rfloor [/mm] gerne nach oben durch c*n mit Konstanter [mm] c\in \IR [/mm] abschätzen.
Oder anders ausgedrückt:
Gibt es ein [mm] c\in \IR [/mm] und [mm] n_{0} \in \IN, [/mm] so dass [mm] \summe_{i=2}^{n} \left\lfloor log_{i}(n)\right\rfloor \le [/mm] c*n [mm] \forall [/mm] n [mm] \ge n_{0} [/mm] ?
Leider weiß ich nicht, ob das überhaupt geht und habe im Moment auch keinen brauchbaren Ansatz und brauche deshalb eure Hilfe.
Grüße,
Ned.
|
|
| |
|
Hiho,
nein geht nicht, da dein erster Summand [mm] $\log_1{n}$ [/mm] schonmal gar nicht definiert ist bzw. existiert.....
MFG,
Gono.
|
|
|
| |
|
Entschuldigung,
war ein kleiner Tippfehler...
Die Summe soll natürlich bei 2 anfangen- habe es jetzt korrigiert.
Geht es denn jetzt?
Grüße Ned.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:23 Do 15.04.2010 | | Autor: | fred97 |
Was bedeuten denn die Klammern
$ [mm] \left\lfloor log_{i}(n)\right\rfloor$
[/mm]
um den Log. ?
FRED
|
|
|
| |
|
Hallo,
die Klammern sind Gaußklammern.
[mm] \left\lfloor x \right\rfloor [/mm] rundet x einfach auf eine ganze Zahl ab.
Grüße,
Ned
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:57 Do 15.04.2010 | | Autor: | abakus |
> Hallo,
>
> ich möchte [mm]\summe_{i=2}^{n} \left\lfloor log_{i}(n)\right\rfloor[/mm]
> gerne nach oben durch c*n mit Konstanter [mm]c\in \IR[/mm]
> abschätzen.
Hallo,
ich weiß nicht, ob es hilft. Aber anstatt Logarithmen mit verschiedenen Basen zu addieren, sollte man vielleicht besser jeweils in die gleiche Basis umformen, also [mm] log_i(n)=\bruch{ln(n)}{ln(i)}
[/mm]
Jeder ln lässt sich nach oben abschätzen mit ln x [mm] \le [/mm] -1+x.
Es ist y=-1+x eine Tangente an der ln-Funktion, und der ln-Graph liegt deshalb darunter.
Gruß Abakus
> Oder anders ausgedrückt:
> Gibt es ein [mm]c\in \IR[/mm] und [mm]n_{0} \in \IN,[/mm] so dass
> [mm]\summe_{i=2}^{n} \left\lfloor log_{i}(n)\right\rfloor \le[/mm]
> c*n [mm]\forall[/mm] n [mm]\ge n_{0}[/mm] ?
> Leider weiß ich nicht, ob das überhaupt geht und habe im
> Moment auch keinen brauchbaren Ansatz und brauche deshalb
> eure Hilfe.
>
> Grüße,
> Ned.
>
>
|
|
|
| |
|
Hallo Abakus,
vielen Dank für deine Mühen, aber mit Deiner Idee komme ich leider nicht weiter.
> Hallo,
> ich weiß nicht, ob es hilft. Aber anstatt Logarithmen mit
> verschiedenen Basen zu addieren, sollte man vielleicht
> besser jeweils in die gleiche Basis umformen, also
> [mm]log_i(n)=\bruch{ln(n)}{ln(i)}[/mm]
> Jeder ln lässt sich nach oben abschätzen mit ln x [mm]\le[/mm]
> -1+x.
> Es ist y=-1+x eine Tangente an der ln-Funktion, und der
> ln-Graph liegt deshalb darunter.
> Gruß Abakus
Auf die Idee den Logarithmus so aufzuschreiben bin ich auch schon gekommen, aber immer wenn ich den Logarithmus durch etwas mit n abschätze (also wie z.B. [mm] ln(n)\le [/mm] -1+n),erhalte ich (durch die Summe) insgesamt eine Abschätzung mit [mm] n^2 [/mm] und nicht mit n.
Oder sehe ich da jetzt etwas nicht, was du siehst?
Grüße Ned.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:59 Do 15.04.2010 | | Autor: | leduart |
Hallo
die Summe ist
[mm] ln(n)*\summe_{i=2}^{n}\bruch{1}{lni}
[/mm]
die Summe kannst du als Integral abschätzen,
[mm] \integral_{3}^{n}{\bruch{1}{lnx} dx}<\summe_{i=2}^{n}\bruch{1}{lni}<\integral_{2}^{n}{\bruch{1}{lnx} dx}
[/mm]
Das Integral heisst li(x), du kannst es genauer bei Wolfran alpha auswerten. du hast dann also als Abschätzung
ln(n)*(li(n)-li(3)) da li(3) und li(2) wenig unterschiedlich sind ist die Abschätzung gut.
ich glaub nicht dass man c*n hinkriegen kann aber c*n*log(n)
Gruss leduart
|
|
|
| |
|
Hallo,
ich möchte mich nochmal bei allen bedanken, die sich mit meinem Problem beschäftigt haben.
Mittlerweile habe ich selber eine Lösung gefunden - es geht (meiner Meinung nach).
Sollte jemand interesse an meiner Lösung haben, poste ich die natürlich gerne. Einfach bescheid sagen.
Grüße Ned.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:18 Do 15.04.2010 | | Autor: | fred97 |
> Hallo,
>
> ich möchte mich nochmal bei allen bedanken, die sich mit
> meinem Problem beschäftigt haben.
>
> Mittlerweile habe ich selber eine Lösung gefunden - es
> geht (meiner Meinung nach).
> Sollte jemand interesse an meiner Lösung haben, poste ich
> die natürlich gerne. Einfach bescheid sagen.
Dann zeig mal Deine Lösung
FRED
>
> Grüße Ned.
>
|
|
|
| |
|
Ok, hier ist sie:
für alle [mm] n\ge [/mm] 16 gilt:
[mm] \summe_{i=2}^{n}\left\lfloor log_{i}(n) \right\rfloor [/mm]
= [mm] \summe_{i=2}^{\wurzel{n}}\left\lfloor log_{i}(n) \right\rfloor [/mm] + [mm] \summe_{i=\wurzel{n}+1}^{n}\left\lfloor log_{i}(n) \right\rfloor [/mm]
[mm] \le \summe_{i=2}^{\wurzel{n}} log_{i}(n) [/mm] + [mm] \summe_{i=\wurzel{n}+1}^{n}\left\lfloor 2*log_{i}(\wurzel{n}) \right\rfloor [/mm]
[mm] \le \summe_{i=1}^{\wurzel{n}}\wurzel{n} [/mm] + [mm] \summe_{i=\wurzel{n}+1}^{n} (2*\left\lfloor log_{i}(\wurzel{n}) \right\rfloor+1) [/mm]
[mm] \le \wurzel{n}*\wurzel{n} [/mm] + [mm] \underbrace{\summe_{i=\wurzel{n}+1}^{n}2*\left\lfloor log_{i}(\wurzel{n}) \right\rfloor}_{=0} [/mm] + [mm] \summe_{1=\wurzel{n}+1}^{n}1\le [/mm] 2n
Bei allen [mm] \wurzel{n}, [/mm] die an den Summen stehen denke man sich die Gaußklammern hinzu. 
Ich hoffe, das ist alles korrekt so.
Grüße Ned.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:46 Do 15.04.2010 | | Autor: | abakus |
> Ok, hier ist sie:
>
> für alle [mm]n\ge[/mm] 16 gilt:
>
> [mm]\summe_{i=2}^{n}\left\lfloor log_{i}(n) \right\rfloor[/mm]
> = [mm]\summe_{i=2}^{\wurzel{n}}\left\lfloor log_{i}(n) \right\rfloor[/mm]
> + [mm]\summe_{i=\wurzel{n}+1}^{n}\left\lfloor log_{i}(n) \right\rfloor[/mm]
> [mm]\le \summe_{i=2}^{\wurzel{n}} log_{i}(n)[/mm] +
> [mm]\summe_{i=\wurzel{n}+1}^{n}\left\lfloor 2*log_{i}(\wurzel{n}) \right\rfloor[/mm]
> [mm]\le \summe_{i=1}^{\wurzel{n}}\wurzel{n}[/mm] +
> [mm]\summe_{i=\wurzel{n}+1}^{n} (2*\left\lfloor log_{i}(\wurzel{n}) \right\rfloor+1)[/mm]
>
> [mm]\le \wurzel{n}*\wurzel{n}[/mm] +
> [mm]\underbrace{\summe_{i=\wurzel{n}+1}^{n}2*\left\lfloor log_{i}(\wurzel{n}) \right\rfloor}_{=0}[/mm]
> + [mm]\summe_{1=\wurzel{n}+1}^{n}1\le[/mm] 2n
>
>
> Bei allen [mm]\wurzel{n},[/mm] die an den Summen stehen denke man
> sich die Gaußklammern hinzu.
>
> Ich hoffe, das ist alles korrekt so.
>
> Grüße Ned.
Hallo,
ein kleiner Einwand: die Summationsindices sind alles natürliche Zahlen.
So etwas kannst du doch nur machen, wenn der Ausdruck [mm] \wurzel{n} [/mm] natürlich ist.
Gruß Abakus
|
|
|
|
