Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Ungleichung

6. Eine Ungleichung zwischen Potenz und Quadrat

Berechnen wir einmal die Werte von <math>2^n</math> und <math>n^2</math> für <math>n=0,\dotsc,10</math>, so bekommen wir schnell die Vermutung, dass <math>2^n \geq n^2</math> für <math>n \geq 4</math> und sogar <math>2^n > n^2</math> für <math>n \geq 5</math> gilt.

<math>\begin{tabular}{c|lllllllllll}
$n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
$2^n$ & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 & 1024 \\
$n^2$ & 0 & 1 & 4 & 9 & 16 & 25 & 36 & 49 & 64 & 81 & 100\end{tabular}</math>

Die Ungleichung <math>\forall n \in \mathds{N}_{\geq 4} (2^n \geq n^2)</math> wollen wir zunächst mit vollständiger Induktion beweisen: Der Induktionsanfang mit <math>n=4</math> ist klar, beide Seiten sind <math>16</math>. Es gelte nun <math>2^n \geq n^2</math>. Dann folgt

<math>\displaystyle 2^{n+1}= 2^n \cdot 2 \geq n^2 \cdot 2 = n^2 + n^2,</math>

und andererseits

<math>\displaystyle (n+1)^2 = n^2 + 2n + 1.</math>

Es würde also reichen, <math>n^2 \geq 2n+1</math> zu zeigen, denn dann folgt <math>2^{n+1} \geq (n+1)^2</math>. Wenn wir jetzt nicht nachdenken wollen, können wir diese Gleichung ebenfalls mit vollständiger Induktion beweisen. Der Induktionsanfang gilt schon für <math>n=3</math>, denn es gilt <math>3^2=9 \geq 7=2 \cdot 3+1</math>. Wenn nun <math>n^2 \geq 2n+1</math> gilt, dann folgt

<math>\displaystyle (n+1)^2 = n^2 + 2n +1  \geq (2n+1)+2n+1=4n+2=2n+(2n+2) \geq 2n+3=2(n+1)+1.</math>

Man kann sich auch etwas geschickter anstellen und die Ungleichung <math>n^2 \geq 2n+1</math> direkt einsehen:

<math>n^2 = n \cdot n \geq n \cdot 3 = 2n + n \geq 2n+1.</math>

Darauf musste man erst einmal kommen.

Es geht aber auch ganz anders, nämlich mit einem kombinatorischen Beweis. Dies bedeutet, dass man mit endlichen Mengen arbeitet (also solche, die mit einer Menge der Form <math>\{1,\dotsc,n\}</math> mit <math>n \in \mathds{N}</math> gleichmächtig sind) und die Anzahl <math>\#</math> ihrer Elemente berechnet (z.B. <math>\#\{\spadesuit,\clubsuit\}=2</math>). Aus Resultaten über endliche Mengen ergeben sich dann Resultate über natürliche Zahlen. Das lässt sich auch alles formalisieren, wenn man allgemeine Rechenregeln wie etwa

<math>\#(A \sqcup B) = \# A + \# B</math>

und

<math>\#(A \times B) = \# A \cdot \#B</math>

beweist (in der Reihenfolge!), für die sich die vollständige Induktion nach <math>\# B</math> anbietet.

Wir beginnen mit der Beobachtung, dass <math>2^n</math> die Anzahl der Teilmengen von <math>\{1,\dotsc,n\}</math> ist (bzw. einer beliebigen <math>n</math>-elementigen Menge). Das sieht man so: Eine Teilmenge von <math>\{1,\dotsc,n+1\}</math> enthält entweder <math>n+1</math> und dann ist der Rest eine Teilmenge von <math>\{1,\dotsc,n\}</math>, oder aber sie enthält <math>n+1</math> nicht und ist ohnehin schon eine Teilmenge von <math>\{1,\dotsc,n\}</math>. Es gibt also doppelt so viele Teilmengen von <math>\{1,\dotsc,n+1\}</math> wie Teilmengen von <math>\{1,\dotsc,n\}</math>. Ferner hat <math>\{1,\dotsc,0\}:=\emptyset</math> genau eine Teilmenge, nämlich <math>\emptyset</math>. Wir sehen also, dass die Anzahl der Teilmengen von <math>\{1,\dotsc,n\}</math> dieselbe Rekursion wie <math>2^n</math> erfüllt und daher mit <math>2^n</math> übereinstimmen muss. Alternativ könnte man auch gleich die allgemeine Rechenregel

<math>\# \mathrm{Abb}(A,B) = \#B^{\# A}</math>

für endliche Mengen <math>A,B</math> beweisen (per Induktion nach <math>\# A</math>) und dann benutzen, dass es eine Bijektion zwischen Abbildungen <math>A \to \{0,1\}</math> und Teilmengen von <math>A</math> gibt, nämlich <math>f \mapsto f^{-1}(\{1\})</math>.

Die Menge <math>\{1,\dotsc,n\}</math> hat genau eine leere Teilmenge, <math>\emptyset</math>, und genau <math>n</math> Teilmengen <math>\{1\},\dotsc,\{n\}</math> mit genau einem Element. Wie viele Teilmengen mit genau <math>2</math> Elementen gibt es? Jedes Paar <math>(i,j)</math> mit <math>1 \leq i,j \leq n</math> und <math>i \neq j</math> liefert eine solche Teilmenge <math>\{1,\dotsc,n\}</math>, aber weil dabei <math>(i,j)</math> und <math>(j,i)</math> dieselbe Teilmenge liefern, gibt es doppelt so viele Paare wie Teilmengen mit <math>2</math> Elementen. Die Anzahl der Paare ist <math>n \cdot (n-1)</math>, weil es nämlich für das <math>i</math> genau <math>n</math> mögliche Wahlen gibt, und dann für <math>j</math> nur noch <math>n-1</math> mögliche Wahlen. Also gibt es <math>\frac{n(n-1)}{2}</math> Teilmengen mit zwei Elementen. Wegen <math>2 < n-2 < n</math> für <math>n \geq 5</math> erhalten wir auch noch die Teilmengen mit <math>n-2</math> Elementen, die aber durch Komplementbildung zu den Teilmengen mit <math>2</math> Elementen korrespondieren. Ihre Anzahl ist also ebenfalls <math>\frac{n(n-1)}{2}</math>. Wir haben damit insgesamt mindestens

<math>1 + n + 2 \cdot \frac{n(n-1)}{2} = n^2+1</math>

Teilmengen gefunden. Es gilt also <math>2^n > n^2</math> für <math>n \geq 5</math>.

Wenn man bereits mit Binomialkoeffizienten vertraut ist (vgl. Abschnitt 10), so kann man dieses Argument auch viel knapper präsentieren:

<math>\displaystyle 2^n = \sum_{k=0}^{n} \binom{n}{k} \geq \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \binom{n}{n-2} = n^2+1.</math>

Und genau hier wird die Stärke dieses Ansatzes klar: Wir können <math>2^n</math> viel genauer nach unten abschätzen und müssen dabei nichts weiter tun, als ein paar Binomialkoeffizienten aufzusummieren. Es handelt sich um keine zufällige Beobachtung, die mit einer Tabelle von Zahlenwerten vermutet und dann per Induktion bestätigt wird, sondern um eine systematische Herleitung. Übrigens gilt noch genauer für <math>n \geq 5</math>

<math>\displaystyle 2^n \geq 2 \binom{n}{0} + 2 \binom{n}{1} + 2 \binom{n}{2} = n^2+n+2,</math>

wobei Gleichheit für <math>n=5</math> gilt.

Kombinatorisch ist übrigens die obige Ungleichung <math>n^2  \geq 2n+1</math> (für <math>n \geq 3</math>) sofort klar. Man muss dafür ja nur <math>2n+1</math> verschiedene geordnete Paare <math>(i,j)</math> mit <math>1 \leq i,j \leq n</math> angeben. Und dafür bieten sich etwa <math>(1,1),\dotsc,(n,1)</math>, <math>(1,2),\dotsc,(n,2)</math> und <math>(1,3)</math> an. Hieran sieht man sehr schön, wie die Kombinatorik den Zahlen und ihrer Arithmetik eine anschauliche Bedeutung gibt und damit den Umgang mit ihnen erleichtert.
 
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]