[Induktion] Beweis dass n < 2^n ist

22.09.2009, 21:10

Empire-Phoenix

[Induktion] Beweis dass n < 2^n ist

Mein Problem ist ich soll per Induktion beweisen, das $\begin{eqnarray*} n < 2^n ; n \in \mathbb N \end{eqnarray*}$ ist.

Induktionsanfang ist dann ja wenn ich n =1 sage $\begin{eqnarray*} 1 < 2^1 \end{eqnarray*}$
Induktionsschritt ist: Wir nehmen an, die Behauptung sei wahr für ein beliebiges aber festes $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$

Und jetzt kommt mein Problem: Wie geht der Induktionsschritt O.o unglücklich

Kann mir jemand helfen in wie weit ich den schreiben muss, im speziellen von wegen des Beweises das $\begin{eqnarray*} n < 2^n \end{eqnarray*}$ ist

22.09.2009, 21:58

Quadratzahl-Jan

Auf diesen Beitrag antworten »

Hi !
Du musst zeigen, dass $\begin{eqnarray*} n+1<2^{n+1} = 2*2^{n} \end{eqnarray*}$ ist,
unter der Voraussetzung, dass $\begin{eqnarray*} n<2^{n} \end{eqnarray*}$ gilt.

23.09.2009, 11:49

Empire-Phoenix

Auf diesen Beitrag antworten »

Gut, soweit verstehe ich das ganze, aber wie kann man so was Beweisen? (Mir fehlen hier vollkommen die möglichen Ansätze nachdem ich jetzt länger rumversucht habe bin ich immer noch nicht weiter gekommen unglücklich

)
Kann mir irgendjemand Ideen geben wie man generell so was beweisen kann?

23.09.2009, 11:53

Mazze

Auf diesen Beitrag antworten »

Zitat:

Kann mir irgendjemand Ideen geben wie man generell so was beweisen kann?

Dafür gibt es kein generelles Rezept, wie der Induktionsschritt aussieht hängt von der Aufgabe ab. Du willst zeigen dass $\begin{eqnarray*} n + 1 < 2^{n+1} \end{eqnarray*}$ gilt. Wegen der Induktionsvoraussetzung ist $\begin{eqnarray*} n < 2^n \end{eqnarray*}$ für ein n,

also folgt natürlich

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

. Jetzt bist Du fast fertig. Ein Schritt fehlt noch.

23.09.2009, 12:24

Empire-Phoenix

Auf diesen Beitrag antworten »

Hm glaube ich verstehe, ich kann mich bei meinen Beweis auf die Vorraussetzung verlassen?

Also wäre dann der letzte schritt die einz wechkürzen ?

sprich

$\begin{eqnarray*} n<2^n \end{eqnarray*}$

womit bewiesen wäre was zu beweisen ist?.

23.09.2009, 12:41

Mazze

Auf diesen Beitrag antworten »

Zitat:

womit bewiesen wäre was zu beweisen ist?.

Du sollst zeigen das $\begin{eqnarray*} n + 1 < 2^{n+1} \end{eqnarray*}$ gilt. Das es ein n gibt für dass $\begin{eqnarray*} n < 2^{n} \end{eqnarray*}$ gilt wissen wir doch bereits. Du musst lediglich noch begründen warum

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

ist, dann bekommst Du nämlich

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

und bist fertig.

23.09.2009, 18:17

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von Empire-Phoenix
Hm glaube ich verstehe, ich kann mich bei meinen Beweis auf die Vorraussetzung verlassen?

Nein, bei deinem Beweis. Und ja, das ist gerade das Prinzip der vollständigen Induktion.

23.09.2009, 21:34

Empire-Phoenix

Auf diesen Beitrag antworten »

Vielen Dank an alle, ich hoffe ich habe es jetzt soweit begriffen smile

23.09.2009, 21:37

Mazze

Auf diesen Beitrag antworten »

Naja, ob Du es begriffen hast würde eine Vervollständigung des Beweises zeigen Augenzwinkern

10.03.2014, 18:52

le_Foo

Auf diesen Beitrag antworten »

Hallo!

Ich grabe diesen alte Thread hier nochmal aus, da ich genau vor dem gleichen Problem stehe.

Zu beweisen ist:

$\begin{eqnarray*} <br /> n < 2^n<br /> \end{eqnarray*}$

Bewiesen habe ich das ganze dann, wenn ich zeigen kann dass ich von n auf n+1 schließen kann indem ich in meine Ungleichung n+1 einsetze und in eine Form bringe die meiner Induktionsannahme entspricht. Korrekt?

Unklar ist mir bei der Erklärung von Mazze, wie man den letzten Schritt beweist:
$\begin{eqnarray*} <br /> 2^n+1 \le 2^{n+1}<br /> \end{eqnarray*}$

Es ist zwar intuitiv logisch aber wie man das formal hinschreibt ist mir noch nicht klar.

lg

10.03.2014, 18:57

10001000Nick1

Auf diesen Beitrag antworten »

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

Weißt du jetzt, wie du $\begin{eqnarray*} 2^n+1\leq 2\cdot 2^n \end{eqnarray*}$ zeigen kannst?

10.03.2014, 18:57

kgV

Auf diesen Beitrag antworten »

dividiere die Ungleichung einfach durch $\begin{eqnarray*} 2^n \end{eqnarray*}$ , um das zu sehen.
Ich glaube aber kaum, dass jemand das explizit bewiesen sehen will, das ist wirklich offensichtlich smile

Alternativ auch einfach $\begin{eqnarray*} 2^{n+1}=2\cdot 2^n=2^n+2^n \end{eqnarray*}$ ausnutzen, und dann subtrahieren

Lg
kgV
Wink

PS. Ist dir bei der Ungleichung von damals alles klar? Wir haben da nie mehr eine Rückmeldung bekommen...

edit: und raus smile

10.03.2014, 19:08

le_Foo

Auf diesen Beitrag antworten »

Tja, es ist wirklich offensichtlich. Ich hab wohl schon Tomaten auf den Augen. Zeit für eine Pause ... smile

Danke für eure Antwort.

@kgV: Die Ungleichung von damals war mir dann klar, dank eurer Hilfe. Ich habe den Thread als abgeschlossen gesehen und daher keine Rückmeldung mehr gegeben.

10.03.2014, 23:03

kgV

Auf diesen Beitrag antworten »

@ le_Foo: schön, dass alles klar geworden ist smile

Bitte melde dich beim nächsten Mal dennoch, damit auch ich den Thread als abgeschlossen betrachten kann smile

11.03.2014, 21:29

le_Foo

Auf diesen Beitrag antworten »

@kgV: Ok mach ich smile

Neue Frage »

Antworten »

[Induktion] Beweis dass n < 2^n ist

Verwandte Themen