Beweis per Induktion

31.10.2013, 21:54

Bäumelinchen

Beweis per Induktion

Hallo, ich soll Folgendes zeigen:

Ich soll die kleinste, natürliche Zahl N bestimmen, sodass für alle n $\begin{eqnarray*} \geq \end{eqnarray*}$ N
$\begin{eqnarray*} 2^{n} > n^{4} \end{eqnarray*}$ gilt.

Meine Idee:

Beweis per vollständiger Induktion:

Ia: n=17 $\begin{eqnarray*} 2^{17} > 17^{4} \end{eqnarray*}$ --> passt.

Iv: Wie oben angegeben

Is: n --> n+1

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

$\begin{eqnarray*} 2^{n+1} = 2*(2)^{n} > 2*(n)^{4} \end{eqnarray*}$ Jetzt habe ich mit 2 multipliziert, weil ich mir dachte, dass ich, wenn ich annehme, dass das geht, weil ich die Seite größer mache und diese trotzdem noch kleiner ist als die linke Seite und das am Ende zeigen kann, stimmt es ja (also nach oben abschätzen)

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

Dabei habe ich eine Information genutzt, die ich in meinem Buch gefunden habe, und zwar, dass

$\begin{eqnarray*} (n^{2} +n^{2} )*(n^{2} +n^{2} )= (n^{2} +2n+1)*(n^{2} +2n+1) \end{eqnarray*}$ ist. Das könnte ich als Nebenschritt/Nebenrechnung aber auch noch einmal mit volltändiger Induktion beweisen und somit herleiten. Die Frage ist jetzt nur, darf ich das alles so machen?! Ich bin mir da echt nicht sicher und hoffe auf eure Hilfe Augenzwinkern

31.10.2013, 22:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Bäumelinchen
Jetzt habe ich mit 2 multipliziert, weil ich mir dachte, dass ich, wenn ich annehme, dass das geht, weil ich die Seite größer mache und diese trotzdem noch kleiner ist als die linke Seite und das am Ende zeigen kann, stimmt es ja (also nach oben abschätzen)

Das ist für dich die Begründung, dass du hier $\begin{eqnarray*} 2n^4 > 4n^4 \end{eqnarray*}$ abschätzt? Das ist natürlich fürchterlich falsch . vergiss das, denn es ist ja auch überhaupt nicht nötig:

Mit sorgfältigeren Abschätzungen solltest du das benötigte $\begin{eqnarray*} 2n^4 > (n+1)^4 \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 17 \end{eqnarray*}$ auch so hinkriegen.

31.10.2013, 22:14

jimmyt

Auf diesen Beitrag antworten »

RE: Beweis per Induktion

Zitat:

Original von Bäumelinchen
...
$\begin{eqnarray*} \dots= (n+1)^{2}*(n+1)^{2} > (n+1)^{4} \end{eqnarray*}$
...

Das kann nicht stimmen, wegen Potenzregel $\begin{eqnarray*} a^p \cdot a^q = a^{p+q} \end{eqnarray*}$ gilt:

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

@HAL 9000 : Sorry, du warst 4 min. schneller.

31.10.2013, 22:17

Bäumelinchen

Auf diesen Beitrag antworten »

Ich sitze da jetzt schon seit Tagen dran, aber finde einfach keine Lösung bzw. weiß nicht, wie ich das sonst abschätzen soll. Hast du einen Tipp für mich?

01.11.2013, 00:59

jimmyt

Auf diesen Beitrag antworten »

RE: Beweis per Induktion
Ok, HAL 9000 hat mir den Thread freundlicherweise überlassen.

Zu allererst:

Zitat:

Original von Bäumelinchen
...
Dabei habe ich eine Information genutzt, die ich in meinem Buch gefunden habe, und zwar, dass

$\begin{eqnarray*} (n^{2} +n^{2} )*(n^{2} +n^{2} )\textcolor{red}{=} (n^{2} +2n+1)*(n^{2} +2n+1) \end{eqnarray*}$ ist.
...

Also von diesem Buch hätte ich gerne mal den Titel gewußt, und zwar deswegen:

$\begin{eqnarray*} (n^{2} +n^{2} ) \cdot (n^{2} +n^{2} ) = (2 n^{2} )^2 = 4 n^{4} ~ \textcolor{red}{\stackrel{???}{=}} ~ (n^{2} +2n+1) \cdot (n^{2} +2n+1) = (n+1)^2 \cdot (n+1)^2 = (n+1)^4 \end{eqnarray*}$

D.h., du bist dabei in deinem Induktionsschritt zu beweisen, dass $\begin{eqnarray*} 2 n^{4} > (n+1)^{4} \end{eqnarray*}$ ist,
und in deinem Buch steht, daß $\begin{eqnarray*} 4 n^{4} = (n+1)^4 \end{eqnarray*}$ gilt. Prost

Ist ja sehr interessant. smile

Aber das nur nebenbei.

Zur Abschätzung beim Induktionsschritt:

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

zu zeigen: $\begin{eqnarray*} 2 n^{4} > n^4 + 4n^3 + 6n^2 + 4n +1 \end{eqnarray*}$

Dabei wird die Transitivität genutzt. Ich beginne mal:

$\begin{eqnarray*} 2 n^{4} = n^{4} + n^{4} > n^4 + 16n^3 = n^4 + 4n^3 + 12n^3>\dots \end{eqnarray*}$

Wegen deinem Induktionsanfang muss $\begin{eqnarray*} n \geq 17 \end{eqnarray*}$ sein. Deswegen $\begin{eqnarray*} n^4 = x \cdot n^3 ~ \Rightarrow ~ x = n \geq 17 \end{eqnarray*}$ .
Vom minimalsten Wert, sprich $\begin{eqnarray*} 17 \end{eqnarray*}$ , ziehe ich noch eins ab, damit $\begin{eqnarray*} 16n^3 < n^4 \end{eqnarray*}$ gilt.

Das musst du jetzt noch zweimal machen mit $\begin{eqnarray*} n^2 \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ und kommst dann fast automatisch auf die richtigen Abschätzungen.

Also weiter geht es jetzt mit der Abschätzung für $\begin{eqnarray*} 12n^3 > x \cdot n^2 ~ \Rightarrow ~ \dots \end{eqnarray*}$

01.11.2013, 14:26

Bäumelinchen

Auf diesen Beitrag antworten »

Also so?:

$\begin{eqnarray*} ... 12n^{3} > 16n^{2} = 6n^{2} + 10n^{2} > 16n =6n+10n > 10n = 1+9 \end{eqnarray*}$

Das mit dem Buch: Da hatte ich gesagt , dass da Folgendes steht: $\begin{eqnarray*} n^{2}+ n^{2} = n^{2}+2n+1 \end{eqnarray*}$ --> Das wurde in den Buch auch per vollständiger Induktion bewiesen.

01.11.2013, 14:31

Bäumelinchen

Auf diesen Beitrag antworten »

Da sollte am Ende kein = sondern ein > natürlich stehen Augenzwinkern

01.11.2013, 17:19

jimmyt

Auf diesen Beitrag antworten »

Sieht gut aus. Und am Ende:

$\begin{eqnarray*} 10n > 1 ~ \Rightarrow ~ n > \frac{1}{10} \end{eqnarray*}$ , und damit bewiesen wegen deinem Induktionsanfang.

Und das mit dem Buch:

$\begin{eqnarray*} n^2 + n^2 ~ \textcolor{red}{\stackrel{???}{=}} ~ n^2 + 2n +1 \end{eqnarray*}$ smile

Test: n=3:

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

$\begin{eqnarray*} 9 + 9 = 9 + 6 + 1 \end{eqnarray*}$

$\begin{eqnarray*} 18 \neq 16 \end{eqnarray*}$

Aber die Abschätzung ist ok. smile

Neue Frage »

Antworten »

Beweis per Induktion

Verwandte Themen