Induktionsbeweis von 2^n > 2n+1

27.01.2009, 21:13

Philipp_Gast

Induktionsbeweis von 2^n > 2n+1

Hallo

Ich würde gerne die Behauptung $\begin{eqnarray*} 2^n > 2n+1 fuer n >= 3 \end{eqnarray*}$ beweisen.

Leider komme ich jedoch nicht so richtig beim Induktionsschritt weiter.

Induktionsannahme:
$\begin{eqnarray*} 2^n > 2n +1 \end{eqnarray*}$

Induktionsschritt:
$\begin{eqnarray*} 2^{n+1} = 2^1 * 2^n = 2(2^n) >= 2(2n+1) (nach der IA) \end{eqnarray*}$

$\begin{eqnarray*} 2^{n+1} >= 4n + 2 >= 2(n+1)+1 = 2n+3 \end{eqnarray*}$

Ich dachte mir 4n+2 ist auf jeden Fall größer oder gleich als 2n+3, weil die Verdopplung des ersten Summanden "mehr wiegt" als die Erhöhung um 1 des zweiten Summanden. Aber diese Begrünung ist ... nun ja ... sehr "fadenscheinig" Big Laugh

Hat jemand eine bessere Idee smile

27.01.2009, 21:32

Dual Space

Auf diesen Beitrag antworten »

RE: Induktionsbeweis von 2^n > 2n+1
Es muss ja nicht immer Induktion sein, oder?

$\begin{eqnarray*} 2^n>2n+1 \Leftrightarrow n>\frac{\log(2n+1)}{\log(2)} \end{eqnarray*}$

27.01.2009, 21:40

Philipp_Gast

Auf diesen Beitrag antworten »

Erstmal danke für die Antwort smile

Wir sind gerade bei der Induktion und wir sollen es eigentlich auch mit ihr lösen.

Aber trotzdem zu deinem Vorschlag:
Wie kommst du denn auf log(2) im Nenner? Reicht nicht n > log(2n+1) ? Die Basis vom Logarithmus wäre dann 2?

Ich wäre aber trotzdem für einen vollständigen Induktionsschritt dankbar. Ich habe das Gefühl, dass ich etwas ganz einfaches übersehe unglücklich

27.01.2009, 21:58

sqrt4

Auf diesen Beitrag antworten »

Deine Schritte sind schon okay. Wenn dus unbedingt noch offensichtlicher willst, dann kannst du zeigen, dass

$\begin{eqnarray*} 4n+2>2n+3 \end{eqnarray*}$ eine wahre Aussage ist.
Und das ist aber klar, da $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$

27.01.2009, 22:05

Philipp_Gast

Auf diesen Beitrag antworten »

Zitat:

Original von sqrt4
Deine Schritte sind schon okay. Wenn dus unbedingt noch offensichtlicher willst, dann kannst du zeigen, dass

$\begin{eqnarray*} 4n+2>2n+3 \end{eqnarray*}$ eine wahre Aussage ist.
Und das ist aber klar, da $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$

Dankeschöön Freude

Wenn meine "Schritte schon okay sind" dann ist das ja gut smile

Ich hätte gedacht, man das sei komplizierter, aber mit dem n >= 3 leuchtet mir ein. Nochmal danke smile

28.01.2009, 14:04

Philipp_Gast

Auf diesen Beitrag antworten »

Also wir haben es heute doch etwas anders gelöst. Falls es jemanden interessiert, ... smile

$\begin{eqnarray*} 2^{n+1} = 2^n * 2 \end{eqnarray*}$

$\begin{eqnarray*} 2^{n+1} > (2n+1)*2 \end{eqnarray*}$

$\begin{eqnarray*} 2^{n+1} > (2(n+1)+1) - (2(n+1)+1) + 2(2n+1) \end{eqnarray*}$

$\begin{eqnarray*} 2^{n+1} > (2(n+1)+1) + (2n-1) \end{eqnarray*}$

$\begin{eqnarray*} 2^{n+1} > (2(n+1)+1) + 5 \end{eqnarray*}$ (Der erste legitime Wert ist ja 3 und 2*3-1 = 5)

Subtrahieren von 5 ergibt erst recht einen kleineren Wert. Also:

$\begin{eqnarray*} 2^{n+1} > 2(n+1)+1 \end{eqnarray*}$

Neue Frage »

Antworten »

Induktionsbeweis von 2^n > 2n+1

Verwandte Themen