Fehler in Induktionsbeweis

14.05.2017, 22:00

Klabautermann

Fehler in Induktionsbeweis

Meine Frage:
Ich habe mich an folgendem Induktionsbeweis (Bild im Anhang) versucht, komme am Ende aber zu keinem befriedigenden Ergebnis.

Wo ist der Fehler oder ist da gar keiner?

Meine Ideen:
Eigentlich würde es mir reichen zu zeigen, dass die Summe < 1 ist. Das habe ich auch zuerst gemacht, dann bekomme ich am Ende aber n < 1 raus, was ja auch falsch ist.

Ich hatte deswegen die Idee, die Grenze nach unten anzupassen und habe 1/n gewählt, mit dem Ergebnis im Bild.

Meine Idee ist jetzt, die Grenze noch geschickter zu wählen, komme da aber nicht weiter.

Hat wirklich niemand eine Idee?

Die Wahl der Waffen ist frei. Es soll nur gezeigt werden, dass die Summe < 1 ist für alle n >= 2.

Ich hatte noch die Idee eine andere Reihe zu finden die gegen 1 konvergiert und deren Glieder alle kleiner sind, als die der Reihe hier.

Zwei Beiträge zusammengefasst, damit es nicht so aussieht, als ob schon jemand antwortet. Steffen

15.05.2017, 10:48

Clearly_wrong

Auf diesen Beitrag antworten »

Ich glaube nicht, dass Induktion die richtige Idee für diese Aufgabe ist.

Wenn es wirklich nur um 1 als Schranke geht und nicht um $\begin{align*} \frac{1}{n} \end{align*}$ , dann ist es nicht so schwierig.

Verwende $\begin{align*} \sum_{k=n+1}^\infty\frac{n!}{k!} \leq \frac{1}{n+1}+\sum_{k=n+2}^\infty\frac{1}{k(k-1)} \end{align*}$ . Die hintere Summe lässt sich als Teleskopsumme darstellen und explizit berechnen.

15.05.2017, 11:05

HAL 9000

Auf diesen Beitrag antworten »

@Clearly_wrong

Hmm, damit kommt man aber nur auf Schranke $\begin{align*} \frac{2}{n+1} \end{align*}$ , zu groß für das angestrebte $\begin{align*} \frac{1}{n} \end{align*}$ . verwirrt

Ich denke da eher an $\begin{align*} \frac{n!}{k!} \leq \frac{1}{(n+1)^{k-n}} \end{align*}$ für alle $\begin{align*} k>n \end{align*}$ , und dann geometrische Reihe.

15.05.2017, 11:08

Clearly_wrong

Auf diesen Beitrag antworten »

Ja, das bezog sich auf

Zitat:

Eigentlich würde es mir reichen zu zeigen, dass die Summe < 1 ist.

[... nicht hinbekommen ...]

Zitat:

Ich hatte deswegen die Idee, die Grenze nach unten anzupassen und habe 1/n gewählt,

Zitat:

Die Wahl der Waffen ist frei. Es soll nur gezeigt werden, dass die Summe < 1 ist für alle n >= 2.

15.05.2017, 11:10

HAL 9000

Auf diesen Beitrag antworten »

Achso. Ich hatte mich auf die erste Zeile mit dem "z.z." im Scan orientiert - und da es ja machbar ist, auch für bare Münze genommen. Augenzwinkern

15.05.2017, 11:13

Clearly_wrong

Auf diesen Beitrag antworten »

Ändert aber nichts daran, dass dein Tipp besser ist. Schneller und präziser. Freude

15.05.2017, 13:29

Klabautermann

Auf diesen Beitrag antworten »

Danke, ihr habt mir sehr geholfen!!

Ich habe es jetzt mit dem Ansatz von HAL9000 gemacht und richtig herausbekommen.

Da ich es aber nicht mag, wenn eine Formel einfach vom Himmel fällt, würde es mich interessieren, wie Du auf diesen Ansatz gekommen bist.

Ich fange mal an: Ich bastle mir eine geometrische Reihe, die gegen 1/n konvergiert:

$\begin{eqnarray*} \sum_{k=n+1}^\infty x^k = \sum_{k=0}^\infty x^k - \sum_{k=0}^n x^k = \frac{1}{1-x} - \frac{x^{n+1}-1}{x-1} = \frac{1}{n} \end{eqnarray*}$

Ich löse das ganze nach x auf und finde die gesuchte Funktion:

$\begin{eqnarray*} \frac{1}{1-x} - \frac{x^{n+1}-1}{x-1} = \frac{x^{n+1}}{1-x}= \frac{1}{n} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow nx^{n+1} + x = 1 \end{eqnarray*}$

Wie löse ich jetzt weiter auf?

Und woher weiß ich aber am Anfang, dass jedes Glied meiner geometrischen Reihe größer ist als bei der gegebenen Reihe oder hoffe ich nur darauf?

15.05.2017, 13:43

HAL 9000

Auf diesen Beitrag antworten »

Also ich diskutiere hier nicht die Summenformel $\begin{align*} \sum_{i=0}^{\infty} q^i = \frac{1}{1-q} \end{align*}$ der geometrischen Reihe (hier angewandt auf $\begin{align*} q=\frac{1}{n+1} \end{align*}$ ), das ist Standardschulwissen. Worüber hier allenfalls zu reden ist, warum die Ungleichung

$\begin{align*} \frac{n!}{k!} \leq \frac{1}{(n+1)^{k-n}} \end{align*}$ für alle $\begin{align*} k>n \end{align*}$

gilt! Und das sieht man durch Kehrwertbildung der linken Seite, denn nach "Kürzen" der Fakultäten bekommt man dort

$\begin{align*} \frac{k!}{n!} = \prod_{j=n+1}^k j \geq \prod_{j=n+1}^k (n+1) = (n+1)^{k-n} \end{align*}$ ,

denn jeder der Faktoren $\begin{align*} j \end{align*}$ im Produkt ist $\begin{align*} \geq n+1 \end{align*}$ , und es sind insgesamt genau $\begin{align*} k-n \end{align*}$ solche Faktoren.

15.05.2017, 14:16

Matt Eagle

Auf diesen Beitrag antworten »

Man könnte auch zunächst umformen:

$\begin{eqnarray*} \sum_{k=n+1}^\infty \frac{n!}{k!}=\sum_{k=1}^\infty\prod_{j=1}^k\frac 1{n+j}. \end{eqnarray*}$

Offenbar kann man die Summanden nun abschätzen

$\begin{eqnarray*} \prod_{j=1}^k \frac 1{n+j} \leq \left(\frac 1{n+1}\right)^k \end{eqnarray*}$

und dann, wie gewünscht, folgern:

$\begin{eqnarray*} \sum_{k=n+1}^\infty \frac{n!}{k!}\leq\sum_{k=1}^\infty \left(\frac 1{n+1}\right)^k=\frac 1n. \end{eqnarray*}$

15.05.2017, 15:26

Klabautermann

Auf diesen Beitrag antworten »

@HAL9000:
Die Summenformel müssen wir auch nicht diskutieren, die habe ich ja in meinem letzten Beitrag auch angewendet. Trotzdem kann ich Deinen Gedankengang bei der Entwicklung nicht nachvollziehen. Ist aber nicht so schlimm. Vielleicht denke ich einfach zu kompliziert und habe am falschen Ende angefangen.

Den zweiten Teil hatte ich selbst schon gefunden.

@Matt Eagle
Danke!! Den Ansatz kann ich sehr gut nachvollziehen. Das war das fehlende Puzzlestück.

15.05.2017, 15:59

HAL 9000

Auf diesen Beitrag antworten »

Dann weiß ich nicht, was du da für Umformungskapriolen anstellst. Vielleicht hast du auch nur verkannt, dass da eine simple Indexverschiebung stattfindet:

$\begin{align*} \sum_{k=n+1}^{\infty} q^{k-n} = \sum_{k=1}^{\infty} q^k \end{align*}$ , und das für $\begin{align*} q=\frac{1}{n+1} \end{align*}$ ,

siehe auch Beitrag von Matt Eagle, der diese Indexverschiebung gleich am Anfang gemacht hat.

15.05.2017, 16:25

Klabautermann

Auf diesen Beitrag antworten »

Ja, es war die Indexverschiebung.

Neue Frage »

Antworten »

Fehler in Induktionsbeweis

Verwandte Themen