Matroids Matheplanet Forum Index
Moderiert von Curufin epsilonkugel
Analysis » Ungleichungen » Ungleichung (rot-schwarz-Baum)
Druckversion
Druckversion
Autor
Universität/Hochschule J Ungleichung (rot-schwarz-Baum)
ProfSnape
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.10.2019
Mitteilungen: 54
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-11-23


Hi!

Bei folgender Ungleichung komme ich beim Umformen ins "Stolpern":


Mein Vorgehen (erstmal auf allen Seiten binären Logarithmus ziehen
(Basis ist daher 2 - schreibe ich aber der Einfachheitshalber nicht dazu) :

fed-Code einblenden

Woher kommt rechts die +1 her?
Oder ergibt sich das gar nicht aus der Umformung, sondern aus der Logik,
dass wenn linke Seite < 2* log(n) ist, dann ist sie "erst recht"
kleiner als 2 * log(n+1) ?

Lg
ProfSnape



Wahlurne Für ProfSnape bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 5735
Herkunft: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-11-23

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Hallo,

wenn ich das richtig verstehe wird da ja einfach nur

\[n\ge 2^{\frac{h(B)}{2}}-1\]
betrachtet und eben nach \(h(B)\) aufgelöst. Dabei kommt naturgemäß zunächst einmal die "-1" mit plus auf die andere Seite...


Gruß, Diophant

PS: ist zwar heutzutage nicht mehr so gebräuchlich, aber es gibt m.W. immer noch das Kürzel \(\on{ld}(x):=\log_2(x)\).


Gruß, Diophant


[Verschoben aus Forum 'Analysis' in Forum 'Ungleichungen' von Diophant]
\(\endgroup\)


Wahlurne Für Diophant bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.10.2019
Mitteilungen: 54
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-11-24


Oops, ich hab da eh vorher falsch umgeformt, als ich den Logarithmus gezogen habe und ein Logarithmus-Gesetz missachtet - zufälligerweise käme aber das selbe rauß^^

Zu deinem Tip: Der Prof hat aber als Tip klar gesagt, dass erstmal auf beiden Seiten der Logarithmus gezogen werden soll, aber sogar wenn ich das mit deinem Tip mache, komme ich nicht auf das richtige Endergebnis - ich gehe wie folgt vor, nachdem ich die '-1' erstmal auf die andere Seite bringe:
fed-Code einblenden

ld 1 ergibt ja 0 und ld 2 ergibt ja 1.

Oops, ich sehe evtl. meinen Fehler:
Als ich den Logarithmus in Zeile 2 ziehe, muss es links sein:
log(n + 1)   ?
Dann würde es am Ende passen...





Wahlurne Für ProfSnape bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1122
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-11-24

\(\begingroup\)\(\newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}}\)
Ja, der Logarithmus ist nicht additiv. (Sonst wäre z.B. $\log(n) = \sum_{k =1}^n \log(1) = 0$ für alle $n$. 🤯)


-----------------
The difference between the novice and the master is that the master has failed more times than the novice has tried. ~ Koro-Sensei
\(\endgroup\)


Wahlurne Für Kezer bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 5735
Herkunft: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-11-24

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
Hallo,

hm, mir ist unklar, was du da gerechnet hast, insbesondere, was du mit der Relation anstellst.

Also, wir haben doch:

\[n\ge 2^{\frac{h(B)}{2}}-1\]
Ein par Umformungen:

\[\ba
n+1&\ge 2^{\frac{h(B)}{2}}\qquad&&\mid\ \text{+1}\\
\\
\log_2(n+1)&\ge \frac{h(B)}{2}\qquad&&\mid\ \text{(die Funktion }\on{log_2(x)}\text{ ist streng monoton steigend)}\\
\\
h(B)&\le 2\log_2(n+1)\qquad&&\mid\ \text{(Ungleichung umgekehrt, mit 2 multipliziert)}
\ea\]
Da solltest du dir wohl die Logarithmengesetze und einige Grundlagen rund um Ungleichungen nochmal ansehen...


Gruß, Diophant
\(\endgroup\)


Wahlurne Für Diophant bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.10.2019
Mitteilungen: 54
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-11-26

\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)
2020-11-24 10:29 - Diophant in Beitrag No. 4 schreibt:
Hallo,

hm, mir ist unklar, was du da gerechnet hast, insbesondere, was du mit der Relation anstellst.

Also, wir haben doch:

\[n\ge 2^{\frac{h(B)}{2}}-1\]
Ein par Umformungen:

\[\ba
n+1&\ge 2^{\frac{h(B)}{2}}\qquad&&\mid\ \text{+1}\\
\\
\log_2(n+1)&\ge \frac{h(B)}{2}\qquad&&\mid\ \text{(die Funktion }\on{log_2(x)}\text{ ist streng monoton steigend)}\\
\\
h(B)&\le 2\log_2(n+1)\qquad&&\mid\ \text{(Ungleichung umgekehrt, mit 2 multipliziert)}
\ea\]
Da solltest du dir wohl die Logarithmengesetze und einige Grundlagen rund um Ungleichungen nochmal ansehen...


Gruß, Diophant

Danke^^

Den Fehler habe ich aber ja bereits selber erkannt - vorheriger Post ganz unten:
"Oops, ich sehe evtl. meinen Fehler:
Als ich den Logarithmus in Zeile 2 ziehe, muss es links sein:
log(n + 1)   ?
Dann würde es am Ende passen..."

Ohne diesen Fehler (log-Gesetz missachtet), sieht bei mir dann die weitere Umformung gnauso aus, wie bei dir.
\(\endgroup\)


Wahlurne Für ProfSnape bei den Matheplanet-Awards stimmen
Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape hat die Antworten auf ihre/seine Frage gesehen.
ProfSnape hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]