log(n)< sqrt(n) beweisen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:30 Fr 04.12.2009 | | Autor: | Probot |
Hallo!
Ich benötige eure Hilfe bei der Lösung einer Aufgabe. Ich komme einfach nicht dahinter:
$f(n)= log(n)$
$g(n)= [mm] \sqrt(n)$
[/mm]
Zeige, dass f Element von o(g) (Klein-o-Notation: "f wächst echt langsamer als g, http://de.wikipedia.org/wiki/Landau-Symbole), indem ein c und ein [mm] n_0 [/mm] Element der Nat.Zahlen konstruiert wird, damit folgende Formel gilt:
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c * g(n)$
Also man muss ein [mm] $n_0$ [/mm] und ein c finden, wo [mm] $\sqrt(n)$ [/mm] immer größer als $log(n)$ ist. Das wäre z.B. $c=1$ und [mm] $n_0=1$. [/mm] Aber wie beweise ich das?
Könntet ihr mir da weiterhelfen?
Danke
PS:
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt: http://www.onlinemathe.de/forum/logn-w%C3%A4chst-langsamer-als-sqrtn-beweisen
|
|
| |
|
> [mm]f(n)= log(n)[/mm]
> [mm]g(n)= \sqrt(n)[/mm]
>
> Zeige, dass f Element von o(g) (Klein-o-Notation: "f
> wächst echt langsamer als g,
> http://de.wikipedia.org/wiki/Landau-Symbole), indem ein c
> und ein [mm]n_0[/mm] Element der Nat.Zahlen konstruiert wird, damit
> folgende Formel gilt:
>
>
> [mm]\forall n, n \in \mathbb{N}, n \geq n_0 : |f(n)| < c * g(n)[/mm]
>
> Also man muss ein [mm]n_0[/mm] und ein c finden, wo [mm]\sqrt(n)[/mm] immer
> größer als [mm]log(n)[/mm] ist. Das wäre z.B. [mm]c=1[/mm] und [mm]n_0=1[/mm]. Aber
> wie beweise ich das?
Hallo Probot,
Vorbemerkung: ich bin nicht ganz sicher, dass du
das mit dem Landau-Symbol genau verstanden hast !
Um zu zeigen, dass deine obige Ungleichung mit [mm] n_0=1 [/mm]
und c=1 passt, könntest du beispielsweise so vorgehen:
1.) zeige, dass f(n)<g(n) für n=1,2,3,4 (durch
einfaches Ausrechnen und Vergleichen der Werte)
2.) Betrachte die Funktionen f(x) und g(x) für reelle x.
Beide sind für alle positiven x differenzierbar.
Zeige dann, dass f'(x)<g'(x) für alle [mm] x\in\IR [/mm] mit x>4 .
Daraus lässt sich dann schließen (wenn es ganz strikt
sein soll, mit Mittelwertsatz), dass f(n)<g(n) auch für
alle n mit n>4 gelten muss.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:05 Fr 04.12.2009 | | Autor: | Probot |
Hallo Al-Ch
danke für die schnelle Antwort.
zu 1) Also für n=1,2,3,4 stimmt die Aussage
zu 2) $f'(x) = [mm] \frac{log(e)}{x}$
[/mm]
$g'(x) = [mm] \frac{1}{2*sqrt(x)}$
[/mm]
Somit muss folgendes gelten: [mm] $\frac{log(e)}{x}<\frac{1}{2*sqrt(x)}$.
[/mm]
Wie zeigt man das? Wenn ich [mm] $\infty$ [/mm] für x einsetze ergibt sich ja folgendes:
[mm] $\frac{log(e)}{\infty}<\frac{1}{2*sqrt(\infty)} \equiv \frac{log(e)}{\infty}<\frac{1}{\infty} \equiv [/mm] log(e) < 1$
Da hier der log eine beliebiege Basis haben kann, kann man dann sagen, dass log(e) immer kleiner als 1 ist?
|
|
|
| |
|
> Hallo Al-Ch
> danke für die schnelle Antwort.
>
> zu 1) Also für n=1,2,3,4 stimmt die Aussage
> zu 2) [mm]f'(x) = \frac{log(e)}{x}[/mm]
> [mm]g'(x) = \frac{1}{2*sqrt(x)}[/mm]
>
> Somit muss folgendes gelten:
> [mm]\frac{log(e)}{x}<\frac{1}{2*sqrt(x)}[/mm].
> Wie zeigt man das? Wenn ich [mm]\infty[/mm] für x einsetze
> ergibt sich ja folgendes:
> [mm]\frac{log(e)}{\infty}<\frac{1}{2*sqrt(\infty)} \equiv \frac{log(e)}{\infty}<\frac{1}{\infty} \equiv log(e) < 1[/mm]
>
> Da hier der log eine beliebiege Basis haben kann,
> kann man dann sagen, dass log(e) immer kleiner als 1 ist?
Guten Abend Probot,
Ich habe mich darauf gestützt, dass die natürlichen
Logarithmen gemeint sind. Dann ist natürlich log(e)=1 !
Die entstehende Ungleichung
$\ [mm] \frac{1}{x}<\frac{1}{2*\sqrt{x}}$
[/mm]
lässt sich sehr leicht nach x auflösen.
Trotzdem ist dies nicht das, was in der vorliegenden
Aufgabe verlangt ist. Um zu zeigen dass $\ [mm] f\in [/mm] o(g)$ ,
kannst du zum Beispiel zeigen, dass [mm] $\limes_{x\to\infty}\frac{f(x)}{g(x)}=0$ [/mm]
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 21:14 Fr 04.12.2009 | | Autor: | Probot |
| Aufgabe | Seien f und g Abbildungen von [mm] $\mathbb{N}$ [/mm] in [mm] $\mathbb{R}$, [/mm] die durch die Gleichungen $f(n) = log(n)$ und $g(n) = [mm] \sqrt(n)$ [/mm] gegeben sind. Zeigen Sie, dass $f [mm] \in [/mm] o(g)$ gilt, d. h.
[mm] $\forall [/mm] c, c [mm] \in \mathbb{R}, [/mm] c > 0 : [mm] \exists n_0, n_0 \in \mathbb{N}: \forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n) $
gilt, indem Sie für beliebiges c > 0 ein [mm] $n_0 \in \mathbb{N}$ [/mm] konstruieren, so dass die Formel
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n)$
erfüllt ist. Die Gültigkeit der ersten Formel ist für das konstruierte [mm] $n_0 [/mm] $ nachzuweisen. |
PS: Ich habe jetzt mal die gesamte Aufgabenstellung angegeben!
---------
Das heißt dann, dass ich den Satz von l'Hospital anwenden kann/muss:
Wenn beide Funktionen nach unendlich gehen:
[mm] $\limes_{n\rightarrow\infty}\frac{f(x)}{g(x)} [/mm] = [mm] \limes_{n\rightarrow\infty}\frac{f'(x)}{g'(x)}$
[/mm]
daraus folgt:
[mm] $\limes_{n\rightarrow\infty}\frac{2*log(e)}{sqrt(n)} [/mm] $
Laut definition von l'Hospital ist das dann das selbe wie [mm] $\frac{c}{\infty}$. [/mm] Dies ist dann 0. Somit wäre der limes für gezeigt. Aber ist damit die Aufgabe gelöst?
Wie beweise ich jetzt, dass ich das richtige [mm] $n_0$ [/mm] gewählt habe? Denn wenn ich für [mm] $n_0$ [/mm] z.B. 0 wähle, darf n auch 0 sein $(n [mm] \geq n_0)$.
[/mm]
Doch für n=0 stimmt die Aussage $|f(n)| < c [mm] \cdot [/mm] g(n)$ nicht:
$|f(0)| = |log(0)| = [mm] \infty$
[/mm]
$g(0) = sqrt(0) = 0$
Hier ist $|f(n)| > c * g(n) $
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Di 08.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
> [mm]f(n)= log(n)[/mm]
> [mm]g(n)= \sqrt(n)[/mm]
>
> Zeige, dass f Element von o(g) (Klein-o-Notation: "f
> wächst echt langsamer als g,
> http://de.wikipedia.org/wiki/Landau-Symbole), indem ein c
> und ein [mm]n_0[/mm] Element der Nat.Zahlen konstruiert wird, damit
> folgende Formel gilt:
>
>
> [mm]\forall n, n \in \mathbb{N}, n \geq n_0 : |f(n)| < c * g(n)[/mm]
Die letzte Angabe besagt doch nur, dass der Funktionswert (!) von f kleiner als ein Vielfaches (!) von dem entsprechenden Funktionswert von g bleibt.
Weil gilt: |5 n|<10*n für alle natürlichen Zahlen könnte man nach deiner obigen Definition nun sagen: "5n wächst echt langsamer als n" !???
Es muss wahrscheinlich so heißen:
[mm] \forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm]
[mm] \exists [/mm] c mit [mm] 0\le [/mm] c <1: |f(n+o)-f(n)| < c * |g(n+o)-g(n)|
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:59 Fr 04.12.2009 | | Autor: | Probot |
Die Angabe müsste eigentlich schon korrekt sein.
Hier die Angabe aus dem Aufgabenblatt:
-------------------
Seien f und g Abbildungen von [mm] $\mathbb{N}$ [/mm] in [mm] $\mathbb{R}$, [/mm] die durch die Gleichungen $f(n) = log(n)$ und $g(n) = [mm] \sqrt(n)$ [/mm] gegeben sind. Zeigen Sie, dass $f [mm] \in [/mm] o(g)$ gilt, d. h.
[mm] $\forall [/mm] c, c [mm] \in \mathbb{R}, [/mm] c > 0 : [mm] \exists n_0, n_0 \in \mathbb{N}: \forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n) $
gilt, indem Sie für beliebiges c > 0 ein [mm] $n_0 \in \mathbb{N}$ [/mm] konstruieren, so dass die Formel
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n)$
erfüllt ist. Die Gültigkeit der ersten Formel ist für das konstruierte [mm] $n_0 [/mm] $ nachzuweisen.
|
|
|
| |
|
Zeige zunächst, dass es zu jedem c ein [mm] n_1 [/mm] gibt, so dass für alle [mm] n>n_1 [/mm] gilt:
[mm] c*\wurzel{n}>\wurzel[4]{n}.
[/mm]
Dan ist [mm] c*\wurzel{n}-log(n)>\wurzel[4]{n}-log(n). [/mm] Zeige nun, dass es ein [mm] n_2 [/mm] gibt, so dass der rechte Teil der Ungleichung für alle [mm] n>n_2 [/mm] positiv wird.
Damit ist für alle n, die gleichzeitig größer als [mm] n_1 [/mm] und [mm] n_2 [/mm] sind, c*wurzel{n}>log(n).
Damit hast du nicht direkt einen Wert von [mm] n_0 [/mm] = [mm] max(n_1|n_2) [/mm] angegeben, aber zumindest einige Eigenschaften davon.
(Aus dem ersten Teil folgt z.B. [mm] n_1 [/mm] > [mm] 1/c^4.)
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:28 Fr 04.12.2009 | | Autor: | Probot |
Danke für die Antwort. Aber mir ist nicht ganz klar, wie ich da vorgehen soll.
Wie kommst du auf diese Formel:
$ [mm] c\cdot{}\wurzel{n}>\wurzel[4]{n}. [/mm] $
Wie kann ich für die angegebenen Formeln zeigen, dass für alle [mm] $n>n_1$ [/mm] bzw. [mm] $n>n_2$?
[/mm]
|
|
|
| |
|
Ich wollte zunächst das c rauswerfen, da es sehr klein oder sehr groß sein kann. Für [mm] n>1/c^4 [/mm] ist [mm] c^4 [/mm] n > 1 und damit [mm] c^4 n^2 [/mm] > n, somit [mm] c*\wurzel{n} [/mm] > [mm] \wurzel[4]{n}.
[/mm]
Jetzt hat man eine Formel unabhängig von c und muss nur noch dasjenige n finden, bei dem [mm] \wurzel[4]{n} [/mm] > log(n) wird. Dabei hängt das n von der Basis des logarithmus ab. Ist dieser z.B. ln, so kann man mit dem Taschenrechner und Ausprobieren bestimmen, dass für n=3 bereits gilt: [mm] \wurzel[4]{3} [/mm] > ln(3).
Das ist zwar auch schon für n=2 erfüllt, aber dabei ist der ln negativ; deswegen sollte man zur Vermeidung von Fallunterscheidungen das n immer größer als die Basis wählen, damit der log positiv wird.
Für log=ln braucht man daher nur das [mm] n_0 [/mm] = max(3 | [mm] 1/c^4) [/mm] zu wählen. Vermutlich tuts auch schon gelegentlich ein kleineres [mm] n_0, [/mm] aber das ist egal. Für c = 1/1000 wählen wir also einfach [mm] n_0 [/mm] = 1 000 000 000 000 und können sicher sein, dass die Bedingung erfüllt ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:25 Sa 05.12.2009 | | Autor: | Probot |
Aber die Aussage [mm] $\wurzel[4]{n}>ln(n)$ [/mm] ist bereits für n=6 nicht mehr korrekt, denn da ist der ln größer als die wurzel.
|
|
|
| |
|
Du hast Recht. Aber für n > 6000 ist ln(n) < [mm] \wurzel[4]{n}.
[/mm]
Du musst also nachweisen, dass für n> 6000 ln(n) < [mm] \wurzel[4]{n} [/mm] ist.
Für andere Basen kann man dann den Beweis sofort übertragen:
[mm] |log_b(n)|< c*\wurzel{n} \gdw |\bruch{ln(n)}{ln(b)}|< c*\wurzel{n} \gdw [/mm] |ln(n)|< [mm] c*|ln(b)|*\wurzel{n} \gdw [/mm] |ln(n)|< [mm] c_1*\wurzel{n} [/mm]
Wobei [mm] c_1=c*|ln(b)| [/mm] ist.
Du musst also nur noch die rote Zeile beweisen. Dann kannst du sagen:
Für n sowohl >6000 als auch [mm] >1/(c*ln(b))^4 [/mm] gilt die Ungleichung.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:14 So 06.12.2009 | | Autor: | dayscott |
wie beweist man die rote Zeile denn ?
|
|
|
| |
|
Es gibt zwei naheliegende Möglichkeiten, die sich beide ähneln:
1. Bilde [mm] f(x)=\wurzel[4]{x}-ln(x) [/mm] und zeige
a) f(6000)>0
b) f'(x)>0 für x>6000
Letzteres bedeutet, dass die Funktion monoton steigt und daher für x>6000
immer >0 bleiben wird, also [mm] \wurzel[4]{x}>ln(x).
[/mm]
2. Bilde f(x) = [mm] \bruch{\wurzel[4]{x}}{ln(x)} [/mm] und zeige
a) f(6000)>1
b) f'(x)>0 für x>6000
Letzteres bedeutet, dass die Funktion monoton steigt und daher für x>6000
immer >1 bleiben wird, also [mm] \wurzel[4]{x}>ln(x).
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:10 So 06.12.2009 | | Autor: | dayscott |
der ln ist bei 2 nicht mehr negativ: http://uploadz.eu/images/13onjeqwta6g18g0zfkt.png
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:16 Fr 04.12.2009 | | Autor: | Probot |
Hier noch nachträglich die Aufgabenstellung:
Seien f und g Abbildungen von [mm] $\mathbb{N}$ [/mm] in [mm] $\mathbb{R}$, [/mm] die durch die Gleichungen $f(n) = log(n)$ und $g(n) = [mm] \sqrt(n)$ [/mm] gegeben sind. Zeigen Sie, dass $f [mm] \in [/mm] o(g)$ gilt, d. h.
[mm] $\forall [/mm] c, c [mm] \in \mathbb{R}, [/mm] c > 0 : [mm] \exists n_0, n_0 \in \mathbb{N}: \forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n) $
gilt, indem Sie für beliebiges c > 0 ein [mm] $n_0 \in \mathbb{N}$ [/mm] konstruieren, so dass die Formel
[mm] $\forall [/mm] n, n [mm] \in \mathbb{N}, [/mm] n [mm] \geq n_0 [/mm] : |f(n)| < c [mm] \cdot [/mm] g(n)$
erfüllt ist. Die Gültigkeit der ersten Formel ist für das konstruierte [mm] $n_0 [/mm] $ nachzuweisen.
|
|
|
| |
|
Na eben.
Nur schade, dass du nicht gleich von Anfang an
die ganze Aufgabe in ihrem vollen Wortlaut ange-
geben hast ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:19 Sa 05.12.2009 | | Autor: | Probot |
Ich dachte mir, ich fasse die Aufgabenstellung etwas zusammen. Aber anscheinend war das ein Fehler von mir. :-(
|
|
|
|
