Vollständige Induktion

20.10.2023, 20:21

Evelyn2003

Vollständige Induktion

Meine Aufgabe ist es folgende Ungleichung $\begin{eqnarray*} 4^n > n^4 \end{eqnarray*}$ mittels vollständige Induktion zu beweisen mit $\begin{eqnarray*} \forall n \geq 5 \end{eqnarray*}$

Induktionsverankerung A(5)

$\begin{eqnarray*} 4^5 > 5^4 \Rightarrow 1024 > 625 \end{eqnarray*}$
Ungleichung gilt für 5.

Induktionsschritt A(n+1)

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

Ich komme nicht weiter... traurig

20.10.2023, 20:44

Malcang

Auf diesen Beitrag antworten »

Es ist
$\begin{eqnarray*} (n+1)^4 = n^4 + 4n^3 + 6n^2 +4n +4 \end{eqnarray*}$
Nun kannst du auf der rechten Seite jeweils $\begin{eqnarray*} n^4\geq n^3, n^4\geq n^2 \end{eqnarray*}$ und so weiter abschätzen. Dann kannst du die IV verwenden.

20.10.2023, 21:06

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Es ist
$\begin{eqnarray*} (n+1)^4 = n^4 + 4n^3 + 6n^2 +4n +4 \end{eqnarray*}$
Nun kannst du auf der rechten Seite jeweils $\begin{eqnarray*} n^4\geq n^3, n^4\geq n^2 \end{eqnarray*}$ und so weiter abschätzen. Dann kannst du die IV verwenden.

also:

Induktionsschritt A(n+1)

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

Abschätzung $\begin{eqnarray*} \forall n \geq 5 \end{eqnarray*}$ (rechte Seite):
$\begin{eqnarray*} n^4\geq 4n^3 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 6n^2 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 4n \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 4 \end{eqnarray*}$

Was wäre denn bitte die Induktionsvoraussetzung? $\begin{eqnarray*} 4^n > n^4 \end{eqnarray*}$ ? Wo setzte ich das aber bitte ein?

Induktionsvoraussetzung

$\begin{eqnarray*} 4^n \cdot 4 > n^4 + 4n^3 + 6n^2 +4n +4 \end{eqnarray*}$

20.10.2023, 22:22

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Evelyn2003
Abschätzung $\begin{eqnarray*} \forall n \geq 5 \end{eqnarray*}$ (rechte Seite):
$\begin{eqnarray*} n^4\geq 4n^3 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 6n^2 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 4n \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 4 \end{eqnarray*}$

Wenn man die summiert, reicht das nicht (ein $\begin{eqnarray*} n^4 \end{eqnarray*}$ zuviel). Es passt eher so:

$\begin{eqnarray*} n^4\geq 5n^3 > 4n^3 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 25n^2 > 6n^2 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 125n > 4n+1 \end{eqnarray*}$

Dies sowie noch ein weiteres $\begin{eqnarray*} n^4 \end{eqnarray*}$ summiert ergibt sich $\begin{eqnarray*} 4n^4 > n^4 + 4n^3 + 6n^2 + 4n + 1 = (n+1)^4 \end{eqnarray*}$ . (<-- EDIT: Schreibfehler bei Exponent korrigiert)

Dies sowie die Induktionsvoraussetzung (IV) baut man nun in den Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ ein:

$\begin{eqnarray*} 4^{n+1} = 4\cdot 4^n \stackrel{IV}{\geq} 4n^4 \stackrel{!}{>} (n+1)^4 \end{eqnarray*}$

20.10.2023, 23:15

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
[quote]Original von Evelyn2003

$\begin{eqnarray*} n^4\geq 5n^3 > 4n^3 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 25n^2 > 6n^2 \end{eqnarray*}$
$\begin{eqnarray*} n^4\geq 125n > 4n+1 \end{eqnarray*}$

Ich habe jetzt jedoch nicht verstanden woher die
$\begin{eqnarray*} 5n^3 \end{eqnarray*}$ ,
$\begin{eqnarray*} 25n^2 \end{eqnarray*}$ ,
$\begin{eqnarray*} 125n \end{eqnarray*}$ ,
$\begin{eqnarray*} 4n+1 \end{eqnarray*}$

kommen? verwirrt

21.10.2023, 10:51

HAL 9000

Auf diesen Beitrag antworten »

Der Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ muss nur für $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ funktionieren, damit kann man dort abschätzen

$\begin{eqnarray*} n^4 = {\color{red}n}\cdot n^3 \geq {\color{red}5}\cdot n^3 \end{eqnarray*}$
$\begin{eqnarray*} n^3 = {\color{red}n}\cdot n^2 \geq {\color{red}5}\cdot n^2 \end{eqnarray*}$
$\begin{eqnarray*} n^2 = {\color{red}n}\cdot n \geq {\color{red}5}\cdot n \end{eqnarray*}$ .

Iteriert bedeutet das $\begin{eqnarray*} n^4\geq 5n^3\geq 25n^2\geq 125n \end{eqnarray*}$ .

Und dass $\begin{eqnarray*} 125n > 4n+1 \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ gilt, das solltest du nun wirklich selbst nachvollziehen können, sonst kannst du das mit dem Beweisen sowieso vergessen.

---------------------------------------------------

Eine alternative Beweismöglichkeit: $\begin{eqnarray*} n\mapsto \left(1+\frac{1}{n}\right)^4 \end{eqnarray*}$ ist für $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ offenkundig streng monoton fallend, daher gilt

$\begin{eqnarray*} \left(1+\frac{1}{n}\right)^4 \leq \left(1+\frac{1}{3}\right)^4 = \frac{256}{81} < 4 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ , umgestellt ergibt das $\begin{eqnarray*} (n+1)^4 < 4n^4 \end{eqnarray*}$ .

Und wenn es für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ gilt, dann speziell auch für alle $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ .

21.10.2023, 13:36

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Dies sowie noch ein weiteres $\begin{eqnarray*} n^4 \end{eqnarray*}$ summiert ergibt sich $\begin{eqnarray*} 4n^4 > n^4 + 4n^3 + 6n^2 + 4n + 1 = (n+1)^5 \end{eqnarray*}$ .

Dies sowie die Induktionsvoraussetzung (IV) baut man nun in den Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ ein:

$\begin{eqnarray*} 4^{n+1} = 4\cdot 4^n \stackrel{IV}{\geq} 4n^4 \stackrel{!}{>} (n+1)^4 \end{eqnarray*}$

Wie kommt man bitte zusätzlich auf die $\begin{eqnarray*} (n+1)^5 \end{eqnarray*}$ ? verwirrt

Zitat:

Original von HAL 9000
$\begin{eqnarray*} 4^{n+1} = 4\cdot 4^n \stackrel{IV}{\geq} 4n^4 \stackrel{!}{>} (n+1)^4 \end{eqnarray*}$

Was bedeutet bitte das Ausrufezeichen über den Ungleichungssymbol? $\begin{eqnarray*} \stackrel{!}{>} \end{eqnarray*}$

Wäre die Aussage nun somit für $\begin{eqnarray*} n+1 \end{eqnarray*}$ gezeigt?

Zitat:

Original von HAL 9000

$\begin{eqnarray*} \left(1+\frac{1}{n}\right)^4 \leq \left(1+\frac{1}{3}\right)^4 = \frac{256}{81} < 4 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ , umgestellt ergibt das $\begin{eqnarray*} (n+1)^4 < 4n^4 \end{eqnarray*}$ .

Und wenn es für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ gilt, dann speziell auch für alle $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ .

Wie kommt man bei der Alternativen Beweismethode auf $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ ? Weshalb wurde nicht beispielsweise $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ genommen oder $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ ?

also

$\begin{eqnarray*} \left(1+\frac{1}{n}\right)^4 \leq \left(1+\frac{1}{4}\right)^4 = \frac{625}{256} \end{eqnarray*}$

oder

$\begin{eqnarray*} \left(1+\frac{1}{n}\right)^4 \leq \left(1+\frac{1}{2}\right)^4 = \frac{81}{16} \end{eqnarray*}$

21.10.2023, 15:17

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Evelyn2003
Wie kommt man bitte zusätzlich auf die $\begin{eqnarray*} (n+1)^5 \end{eqnarray*}$ ? verwirrt

Das ist ein offenkundiger Schreibfehler und soll $\begin{eqnarray*} (n+1)^4 \end{eqnarray*}$ heißen. Augenzwinkern

Nirgendwo in dieser Aufgabe spielen fünfte Potenzen eine Rolle.

Zitat:

Original von Evelyn2003
Wie kommt man bei der Alternativen Beweismethode auf $\begin{eqnarray*} n \geq 3 \end{eqnarray*}$ ? Weshalb wurde nicht beispielsweise $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ genommen oder $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ ?

Weil es erst ab n=3 klappt - oder ist etwa $\begin{eqnarray*} \frac{81}{16} < 4 \end{eqnarray*}$ ??? Na also.

Zitat:

Original von Evelyn2003
Was bedeutet bitte das Ausrufezeichen über den Ungleichungssymbol? $\begin{eqnarray*} \stackrel{!}{>} \end{eqnarray*}$

Nichts weiter als dass dieses > einer besonderen Aufmerksamkeit bedarf. Erkennst du denn nicht selbst, dass das genau die Ungleichung ist, die unmittelbar vorher bewiesen wurde? unglücklich

22.10.2023, 02:21

Evelyn2003

Auf diesen Beitrag antworten »

Ich danke dir, HAL. Ich habe es hiermit verstanden. smile

Kannst du mir vielleicht auch bei der folgenden Beweisaufgabe helfen? verwirrt

$\begin{eqnarray*} \forall n \in \mathbb N : 5^{2n} - 3^{2n} \end{eqnarray*}$ ist ohne Rest durch $\begin{eqnarray*} 8 \end{eqnarray*}$ teilbar.

Induktionsverankerung $\begin{eqnarray*} A(1) \end{eqnarray*}$

$\begin{eqnarray*} 8| (5^{2 \cdot 1} - 3^{2 \cdot 1}) = 8| (25 - 9) = 8| 16 = 2 \end{eqnarray*}$

$\begin{eqnarray*} 16 \end{eqnarray*}$ durch $\begin{eqnarray*} 8 \end{eqnarray*}$ ist ohne Rest teilbar. Somit gilt die Gleichung für $\begin{eqnarray*} n=1 \end{eqnarray*}$

Induktionsschritt $\begin{eqnarray*} A(n+1) \end{eqnarray*}$

$\begin{eqnarray*} 8| (5^{2 \cdot (n+1)} - 3^{2 \cdot (n+1)}) = 8| (5^{2n+2} - 3^{2n+1}) = 8| (5^{2n} \cdot 5^2 - 3^{2n} \cdot 3) = 8| (5^2 \cdot 5^{2n} - 3^{2n} \cdot 3) \end{eqnarray*}$

Wie erfolgt bitte die Abschätzung hierbei?

22.10.2023, 11:13

Malcang

Auf diesen Beitrag antworten »

Mach dazu bitte einen neuen Thread auf. Vielleicht kann ein Moderator dies in einen eigenen Thread verschieben?

Aber zur Aufgabe:
Es ist $\begin{eqnarray*} 5^{2(n+1)} - 3^{2(n+1)} = 25\cdot5^{2n} - 9\cdot 3^{2n} \end{eqnarray*}$
Wir sehen, dass sowohl $\begin{eqnarray*} 25 \end{eqnarray*}$ als auch $\begin{eqnarray*} 9 \end{eqnarray*}$ bei der Division durch $\begin{eqnarray*} 8 \end{eqnarray*}$ jeweils den Rest $\begin{eqnarray*} 1 \end{eqnarray*}$ lassen. Aber wie können wir ihn extrahieren?
Durch $\begin{eqnarray*} 25 = 24 + 1 \end{eqnarray*}$ und $\begin{eqnarray*} 9 = 8+1 \end{eqnarray*}$ .
Also: $\begin{eqnarray*} 5^{2(n+1)} - 3^{2(n+1)} = (24+1)\cdot5^{2n} - (8+1)\cdot 3^{2n} = ... \end{eqnarray*}$

22.10.2023, 14:37

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Also: $\begin{eqnarray*} 5^{2(n+1)} - 3^{2(n+1)} = (24+1)\cdot5^{2n} - (8+1)\cdot 3^{2n} = ... \end{eqnarray*}$

Danke für deine Zeit, Malcang. Wink

$\begin{eqnarray*} 5^{2(n+1)} - 3^{2(n+1)} = (24+1)\cdot5^{2n} - (8+1)\cdot 3^{2n} = 24 \cdot 5^{2n} + 5^{2n} - (8 \cdot 3^{2n} + 3^{2n}) = 24 \cdot 5^{2n} + 5^{2n} - (8 \cdot 3^{2n} + 3^{2n}) = 24 \cdot 5^{2n} + 5^{2n} - 8 \cdot 3^{2n} - 3^{2n} = 24 \cdot 5^{2n} - 8 \cdot 3^{2n} + 5^{2n} - 3^{2n} \end{eqnarray*}$

nach IV ist der letzte Term $\begin{eqnarray*} 5^{2n} - 3^{2n} \end{eqnarray*}$ dann durch 8 teilbar und die zwei übrig gebliebenen Produkte ebenso, da Sie zum einen mit der 8 multipliziert werden und die 8 ebenso Teiler von 24 ist. Wäre das die richtige Argumentation oder müsste man statt der 8, mit den Primfaktorzerlegung argumentieren, das 2 teiler von 8 wäre und somit teiler von 24?

22.10.2023, 15:21

Malcang

Auf diesen Beitrag antworten »

Das trifft zwar den Kern, aber für mich liest es sich unnötig kompliziert. Es ist
$\begin{eqnarray*} 24 \cdot 5^{2n} - 8 \cdot 3^{2n} + 5^{2n} - 3^{2n} = (24\cdot 5^{2n} -8\cdot 3^{2n}) +(5^{2n} -3^{2n}) \end{eqnarray*}$

Über die zweite klammer hast du schon korrekt mit der IV argumentiert.
Für die erste Klammer finden wir ein ganz einfaches Argument, warum der Term durch 8 teilbar ist.

22.10.2023, 15:39

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang

Über die zweite klammer hast du schon korrekt mit der IV argumentiert.
Für die erste Klammer finden wir ein ganz einfaches Argument, warum der Term durch 8 teilbar ist.

Dann würde ich sagen: Weil 24 ein ganzahliges vielfaches von 8 ist?

$\begin{eqnarray*} 24 \cdot 5^{2n} - 8 \cdot 3^{2n} + 5^{2n} - 3^{2n} = (24\cdot 5^{2n} -8\cdot 3^{2n}) +(5^{2n} -3^{2n}) =((8 \cdot 3) \cdot 5^{2n} -8\cdot 3^{2n}) +(5^{2n} -3^{2n}) \end{eqnarray*}$

22.10.2023, 15:41

Malcang

Auf diesen Beitrag antworten »

Aber das alleine ist ja nicht die Argumentation, warum der Term in der Klammer durch 8 teilbar ist.

22.10.2023, 15:47

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Aber das alleine ist ja nicht die Argumentation, warum der Term in der Klammer durch 8 teilbar ist.

8 ausklammern?

$\begin{eqnarray*} =((8 \cdot 3) \cdot 5^{2n} -8\cdot 3^{2n}) +(5^{2n} -3^{2n}) =8 \cdot ( 3 \cdot 5^{2n} - 3^{2n}) +(5^{2n} -3^{2n}) \end{eqnarray*}$

22.10.2023, 15:52

Malcang

Auf diesen Beitrag antworten »

Fertig.

22.10.2023, 15:59

HAL 9000

Auf diesen Beitrag antworten »

Die Behauptung ist an sich unnötig schwach formuliert:

Via $\begin{eqnarray*} 5^{2n+2} - 3^{2n+2} = 25\cdot 5^{2n} - 9\cdot 3^{2n} = 16\cdot 5^{2n} + 9\cdot \left( 5^{2n} - 3^{2n} \right) \end{eqnarray*}$ im Induktionsschritt lässt sich problemlos die Teilbarkeit durch 16 statt nur durch 8 hier nachweisen.

22.10.2023, 16:54

Evelyn2003

Auf diesen Beitrag antworten »

Danke nochmals an euch beide! ihr wart für mich eine große Hilfe. Wink

22.10.2023, 21:41

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
[quote]Original von Evelyn2003

Dies sowie noch ein weiteres $\begin{eqnarray*} n^4 \end{eqnarray*}$ summiert ergibt sich $\begin{eqnarray*} 4n^4 > n^4 + 4n^3 + 6n^2 + 4n + 1 = (n+1)^4 \end{eqnarray*}$ . (<-- EDIT: Schreibfehler bei Exponent korrigiert)

Bin doch noch etwas gerade verwirrt. Wie bist du denn bitte auf die $\begin{eqnarray*} 4n^4 \end{eqnarray*}$ gekommen?

23.10.2023, 08:21

HAL 9000

Auf diesen Beitrag antworten »

Schwer fassbar, dass du nach diesen langen ausführlichen Erläuterungen immer noch derart blind durch den Beweis stolperst. unglücklich

Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ muss die Ungleichung $\begin{eqnarray*} 4^{n+1} \geq \left(n+1\right)^4 \end{eqnarray*}$ nachgewiesen werden, im Verlauf dieses Beweises wird irgendwann die Induktionsvoraussetzung $\begin{eqnarray*} {\color{red}4^n \geq n^4} \end{eqnarray*}$ benutzt. Und diese den Induktionsschritt bildende Ungleichungskette startet eben mit

$\begin{eqnarray*} 4^{n+1} = 4\cdot {\color{red} 4^n \geq~} 4\cdot {\color{red}n^4}~\geq \ldots \end{eqnarray*}$

Steht alles schon oben - und du fragst immer noch "wie bist du denn auf die $\begin{eqnarray*} 4n^4 \end{eqnarray*}$ gekommen". Finger1

P.S.: Übrigens hast du das ganze auch noch im falschen Thread gepostet.

23.10.2023, 10:24

Equester

Auf diesen Beitrag antworten »

Der Thread dürfte der richtige sein. Es wurden unüblicherweise zwei Aufgaben in einem Thread bearbeitet.

@Evelyn: Bitte pro Aufgabe einen Thread. Für die bessere Übersicht Augenzwinkern

23.10.2023, 11:15

HAL 9000

Auf diesen Beitrag antworten »

Ja genau, den Überblick hatte ich verloren - ich dachte, es geht in dem Thread jetzt nur noch um die Teilbarkeitsaufgabe.

23.10.2023, 14:49

Evelyn2003

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ muss die Ungleichung $\begin{eqnarray*} 4^{n+1} \geq \left(n+1\right)^4 \end{eqnarray*}$ nachgewiesen werden, im Verlauf dieses Beweises wird irgendwann die Induktionsvoraussetzung $\begin{eqnarray*} {\color{red}4^n \geq n^4} \end{eqnarray*}$ benutzt. Und diese den Induktionsschritt bildende Ungleichungskette startet eben mit

$\begin{eqnarray*} 4^{n+1} = 4\cdot {\color{red} 4^n \geq~} 4\cdot {\color{red}n^4}~\geq \ldots \end{eqnarray*}$

Steht alles schon oben - und du fragst immer noch "wie bist du denn auf die $\begin{eqnarray*} 4n^4 \end{eqnarray*}$ gekommen". Finger1

Dankeschön. Jetzt habe ich es gänzlich verstanden smile

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen