Vergleichssatz mit vollständiger Induktion

07.10.2012, 21:05

krypt0n11

Auf diesen Beitrag antworten »

Vergleichssatz mit vollständiger Induktion

Meine Frage:
Hallo zusammen, habe wieder mal ein Problem...
Und zwar soll ich mit vollständiger Induktion beweisen, dass für alle natürlichen Zahlen $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ gilt: $\begin{eqnarray*} \frac{n(n+1)}{2^{n}}\leq \frac{4}{n-1} \end{eqnarray*}$

Schliessen Sie nun, dass $\begin{eqnarray*} \lim_{n \to \infty } \frac{n^{2} }{2^{n} } = 0 \end{eqnarray*}$

Meine Ideen:
Also ich habe als erstes die Induktionsverankerung für n=4 gemacht. Dabei kommt heraus das $\begin{eqnarray*} \frac{20}{16}\leq \frac{4}{3} \end{eqnarray*}$
Also stimmt die Verankerung.
Dannach habe ich für n --> n+1 eingesetzt und ausmultipliziert, dabei komme ich auf $\begin{eqnarray*} \frac{n^{3} +3n^{2}+2n}{2^{(n+1)} } \leq 4 \end{eqnarray*}$
Wie komme ich von hier aus weiter und was soll ich hier mit dem Vergleichssatz anfangen, der im Aufgabentitel steht?

07.10.2012, 21:13

Cheftheoretiker

Auf diesen Beitrag antworten »

RE: Vergleichssatz mit vollständiger Induktion
Hi,

bring die 4 auf die andere Seite und zeige das der linke Ausdruck kleiner gleich 0 ist. smile

smile

07.10.2012, 21:23

krypt0n11

Auf diesen Beitrag antworten »

Ok, dann versuch ichs nochmal^^

Im Prinzip steht ja dann der genau gleiche Ausdruck da einfach -4 und das soll dann kleiner gleich Null sein. Iregndwo in meinen Unterlagen habe ich gelesen das der $\begin{eqnarray*} \lim_{n \to \infty } q^{n}= 0 \end{eqnarray*}$ ist, stimmt das? Dann wäre ja logischerweise der ganze vordere Ausdruck = 0 - 4 = -4
Ist das so als Beweis korrekt?

07.10.2012, 21:30

Cheftheoretiker

Auf diesen Beitrag antworten »

Jap, die 4 wird auf die andere Seite gebracht so das dort $\begin{eqnarray*} \frac{n^{3} +3n^{2}+2n}{2^{(n+1)} }-4 \leq 0 \end{eqnarray*}$ steht. Ob die Argumentation so durchgeht weiß ich nicht. verwirrt

verwirrt

Ich würde den Ausdruck auf einen Hauptnenner bringen und anschließend damit argumentieren, dass der Ausdruck kleiner gleich 0 sein muss (Entweder Zähler immer kleiner gleich 0 und Nenner größer Null oder Zähler größer gleich 0 und Nenner kleiner Null.)

07.10.2012, 22:04

krypt0n11

Auf diesen Beitrag antworten »

Also dann bringe ich das ganze noch auf einen Hauptnenner, dann bekomme ich:
$\begin{eqnarray*} \frac{n^{3} +3n^{2} +2n-4*(2^{(n+1)}) }{2^{n+1} } \leq 0 \end{eqnarray*}$
Dann müsste ich jetzt noch nur noch die ober Gleichung Null setzen und die untere auch?
Also der Nenner kann ja nur 0 sein wenn $\begin{eqnarray*} n\leq -1 \end{eqnarray*}$ ist, dass ist aber nicht möglich, da $\begin{eqnarray*} n\leq 4 \end{eqnarray*}$ von Anfang an ausgeschlossen wurden. Wie finde ich heraus wann der Zähler = 0 ist, das scheint mir ja ne komplizierte Gleichung zu sein, oder gibt es da einen Trick?

07.10.2012, 22:11

Cheftheoretiker

Auf diesen Beitrag antworten »

Naja, die einzige Möglichkeit die noch besteht das der Ausdruck kleiner oder gleich Null wird ist das der Zähler kleiner oder gleich $\begin{eqnarray*} 0 \end{eqnarray*}$ ist.

$\begin{eqnarray*} n^3+3n^2+2n-4(2^{n+1})\leq 0 \end{eqnarray*}$

$\begin{eqnarray*} n^3+3n^2+2n-2^2\cdot 2^{n+1}\leq 0 \end{eqnarray*}$

$\begin{eqnarray*} n^3+3n^2+2n-2^{n+3}\leq 0 \end{eqnarray*}$

Nun musst du argumentieren warum der Zähler kleiner gleich $\begin{eqnarray*} 0 \end{eqnarray*}$ ist. smile

smile

Anzeige

07.10.2012, 23:03

krypt0n11

Auf diesen Beitrag antworten »

Man müsste den Limes von n gegen (+)Unendlich anschauen, gegen Null und (-)Unendlich ist ja laut Aufgabe verboten...
Also:
$\begin{eqnarray*} \lim_{n \to \infty } n^{3}+3n^{2}+2n-2^{n+3} \end{eqnarray*}$
Dann rechne ich durch n^3 und komme auf:
$\begin{eqnarray*} \lim_{n \to \infty } 1+\frac{3}{n} +\frac{2}{n^{2} } -\frac{2^{n+3}}{n^{3} } \end{eqnarray*}$

die beiden mittleren Ausdrücke müssen gegen Null gehen, somit müsste dann gelten:
$\begin{eqnarray*} 1\leq \frac{2^{n+3}}{n^{3}} \end{eqnarray*}$

Hier komme ich dann wieder nicht mehr weiter, oder bin ich da auf dem Holzweg?

07.10.2012, 23:26

Iorek

Auf diesen Beitrag antworten »

RE: Vergleichssatz mit vollständiger Induktion

Zitat:

Original von krypt0n11
Dannach habe ich für n --> n+1 eingesetzt und ausmultipliziert, dabei komme ich auf $\begin{eqnarray*} \frac{n^{3} +3n^{2}+2n}{2^{(n+1)} } \leq 4 \end{eqnarray*}$

Das hast du bestimmt nicht da stehen, das ist nämlich schon falsch. unglücklich

unglücklich

07.10.2012, 23:35

Cheftheoretiker

Auf diesen Beitrag antworten »

RE: Vergleichssatz mit vollständiger Induktion
Dann ist wohl die weitere Rechnung (und Mühe) auch vergebens. geschockt

geschockt

07.10.2012, 23:37

krypt0n11

Auf diesen Beitrag antworten »

Habs nochmal nachgerechnet komm aber genau auf dieses Resultat.
Ich habe überall n+1 eingesetzt, ausmultipliziert und dann noch das n von der anderen Seite rübermultipliziert... Ist das falsch?

08.10.2012, 07:19

Iorek

Auf diesen Beitrag antworten »

Ich habe das fehlende $\begin{eqnarray*} n \end{eqnarray*}$ im Nenner übersehen, damit ist die Umformung zwar richtig, der weitere Weg aber nicht unbedingt das Gelbe vom Ei. Den Grenzwert für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ zu betrachten ist ein Trugschluss, da du bei der Grenzwertbestimmung wahrscheinlich die zu beweisende Aussage benutzen würdest bzw. die danach stehende $\begin{eqnarray*} \lim\limits_{n\to\infty} \frac {n^2}{2^n} =0 \end{eqnarray*}$ verwenden würdest. Stattdessen solltest du im Induktionsschritt lieber mit $\begin{eqnarray*} \frac{(n+1)(n+2)}{2^{n+1}} \end{eqnarray*}$ anfangen, und durch Abschätzungen nach oben auf $\begin{eqnarray*} \frac 4n \end{eqnarray*}$ kommen.

08.10.2012, 17:34

BioKai

Auf diesen Beitrag antworten »

Hey ich stecke genau bei der gleichen Aufgabe fest!! >.<

Ich hab keine bessere Idee, weil ich vieles schon versucht und nicht geschaft hab, aber ich glaub schon der Loesungsansatz ist daher falsch, dass man nicht einfach ueberall n+1 einsetzen kann um auf die Loesung zu kommen...

08.10.2012, 17:47

Cheftheoretiker

Auf diesen Beitrag antworten »

Wenn mein Ansatz nicht zum Ziel führt, dann darf gerne jemand anders weiter machen. smile

smile

08.10.2012, 18:10

lgrizu

Auf diesen Beitrag antworten »

@Biokai:

Wo genau steckst du fest? Was hast du bisher?

08.10.2012, 18:48

mYthos

Auf diesen Beitrag antworten »

Wahrscheinlich ist der Weg über die Multiplikation der Ungleichung mit dem gemeinsamen Nenner erfolgversprechender.
Dann ist als I.V.

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

und unter deren Verwendung zu zeigen, dass

$\begin{eqnarray*} \ldots \end{eqnarray*}$

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

Bei dieser Rechnung ergibt sich die Richtigkeit erst ab $\begin{eqnarray*} n \geq 4 \end{eqnarray*}$ , wie auch im Aufgabentext gefordert, nichtsdestoweniger gilt die ursprünglich angegebene Ungleichung bereits ab n = 2. Man zeigt daher anfangs einfach die Richtigkeit hintereinander für n = 2, 3, 4

mY+

09.10.2012, 17:30

krypt0n11

Auf diesen Beitrag antworten »

Ok da bin ich jetzt nicht ganz mit gekommen verwirrt

verwirrt

Also ich glaube ich habe es immerhin soweit geschafft zu zeigen, dass $\begin{eqnarray*} \lim_{n%20\to%20\infty%20}%20\frac{n^{2}%20}{2^{n}%20}%20=%200 \end{eqnarray*}$ ist.
Man kann nämlich ,wenn man die Formel der vollständigen Induktion für n --> n+1 benutzt, auf die Formel $\begin{eqnarray*} \frac{n^{2} }{2^{n} } \leq \frac{8}{n} - \frac{3n}{2^{n}}- \frac{2}{2^{n} } \end{eqnarray*}$ umformen. Wenn man jetzt den Grenzwert der rechten Seite betrachtet (man muss dann noch mit (1/x) multiplizieren, damit dass n vom zweiten Ausdruck weg ist), dass (8/(n^2)) und -(2/(n*2^n)) gegen Null konvergieren. Der Ausdruck -(3/(2^n) muss auch gegen 0 konvergieren, da 2^n gegen Unendlich konvergiert und 3 konstant ist.

Nun steht dann da: $\begin{eqnarray*} \lim_{n \to \infty } \frac{8}{n^{2} } - \frac{3}{2^{n}}- \frac{2}{n2^{n} } \geq 0 \geq \lim_{n \to \infty } \frac{n^{2} }{2^{n} } \end{eqnarray*}$
Stimmt das immerhin halbwegs?

Wenn ja, dann wäre ich froh, wenn mir mYthos , oder jemand anderes der seinen Beweis/Tip versteht, ihn mir erklären könnte Erstaunt2

Erstaunt2

09.10.2012, 17:46

Gastt

Auf diesen Beitrag antworten »

Hmh, mir ist nicht so ganz klar was Du da anstellst...
Warum hältst Du Dich nicht einfach an die Anleitung aus der Aufgabenstellung und zeigst zunächst, induktiv, die Ungleichung aus der die eigentlich zu zeigende Aussage per Einschließungskriterium direkt folgt?
Hast Du die Vollständige Induktion denn grundsätzlich verstanden?

Im konkreten Fall ist ja im Induktionsschritt zu zeigen, dass unter Voraussetzung von

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

folgt, dass:

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

Betrachte also:

$\begin{eqnarray*} \frac{(n+1)(n+2)}{2^{n+1}}=\frac{n(n+1)}{2^n}\cdot\frac{n+2}{2n}<\ldots<\frac 4n. \end{eqnarray*}$

09.10.2012, 17:53

krypt0n11

Auf diesen Beitrag antworten »

Ah ok^^ Das reicht schon?! Auf das bin vor ner Stunde gekommen. Oh mann -.-
Wie die vollständige Induktion funktioniert ist mir schon klar. Ich weiss meistens nur nicht auf welchen Ausdruck ich umformen soll und was schon als Beweis ausreicht (oder auch nicht^^)

Auf jeden Fall vielen Dank smile

smile

09.10.2012, 17:58

Gastt

Auf diesen Beitrag antworten »

Na ja, das reicht noch nicht ganz.

Die Punkte, in der Ungleicungskette hier

$\begin{eqnarray*} \frac{n(n+1)}{2^n}\cdot\frac{n+2}{2n}<\ldots<\frac 4n \end{eqnarray*}$

musst Du unter Nutzung der Induktionsvoraussetzung und einer elementaren Abschätzung schon noch mit 'Fleisch' füllen.

09.10.2012, 18:19

krypt0n11

Auf diesen Beitrag antworten »

Hmm... Ich bin sowieso wieder hängen geblieben, das ist deprimierend -.-
Ich hab das versucht nachzurechnen, wie kommt man auf diesen Ausdruck überhaupt?
Für mich ist da irgendwo ein n zuviel? Vom 4/n wirst du's ja nicht rübergeholt haben, sonst ginge ja auch der zu erreichende Ausdruck kaputt... Und wie kommst du auf die (2^n)*(2n)=2^(n+1)?

09.10.2012, 18:26

BioKai

Auf diesen Beitrag antworten »

Hey neenee du siehst das falsch! Dieses lim n^2/2^n beweist du mit dem Vergleichssatz! Siehe Skript 2.10 (glaub isses)... dann nimmst du als an die Nullmenge bzw. die Menge der Nullen für bn die n^2/2^n und als cn diese 4/n-1...

da die Nullmenge Null ist und 4/n-1 gegen Null geht muss bn auch gegen null gehen!

09.10.2012, 18:27

krypt0n11

Auf diesen Beitrag antworten »

Ah doch ich glaube ich kanns nachvollziehen^^
Stimmt das?
Man klammert n*(n+1) aus (aus n^2+3n+2) und dann bleibt da noch ein *2n übrig die Zwei streicht man mit dem 2^1*2^n weg. Müsste dann aber nicht auf der rechten Seite stehen <=4/n^2?

09.10.2012, 18:38

BioKai

Auf diesen Beitrag antworten »

Hallo!
Ich dachte eigentlich auch, dass ich die Induktion vollständig verstanden hab, aber da ich im letzten Übungsblatt irgendwie alle Induktionen falsch gemacht hab zweifle ich wieder daran...
Ich hätte da mal ne Frage: Und zwar, reicht es wirklich beim IS auf beiden Seiten für n dann n+1 einzusetzen?
Unser Tutor hat da nämlich komische Sachen angestellt, er hatte z.B. einmal links stehen 2^(n+5). Als IS hat er dann (natürlich) 2^(n+6) gemacht und daraus 2*2^(n+5).
So, jetzt das verwirrende: Auf der RECHTEN Seite stand (n+4)!. Und er hat dann NICHT (wie ich) ((n+1)+4)! daraus gemacht sondern: (n+4)!*2...

Und da steig ich aus... wann darf ich auf beiden Seiten aus n einfach n+1 machen und wann muss ich einen Faktor oder Summand finden??

Wäre toll wenn mir das jemand sagen könnte... immer wenn ich denke "JETZT hab ich die Induktion geschnallt" kommt ne Aufgabe, die alles wieder kaputt macht... unglücklich

unglücklich

10.10.2012, 08:47

lgrizu

Auf diesen Beitrag antworten »

Auf beiden Seiten einfach n+1 einsetzen funktioniert nicht.

Man sollte stets auf einer Seite anfangen und dann so lange umformen, bis man die Induktionsvorraussetzung anwenden kann.

Ich habe letztens auch einen Thread betreut, da hatte der Fragesteller ähnliche Probleme, wie du, vielleicht schaust du dir den einmal an: Vollständige Induktion

10.10.2012, 17:45

BioKai

Auf diesen Beitrag antworten »

Heeey!

Ich habe neue Lösungsansätze:

1. Umformen, dass (n(n+1)(n-1))/4 >= 2^n da steht, dann 2^n "induzieren":
n -> n+1: 2^(n+1) = 2^n * 2

Also Faktor 2 benutzen für die andere Seite und Ungleichung aufstellen:

(2n(n+1)(n-1))/4 <= 2^n*2
<=> (n(n+1)(n-1))/2 <= 2^n*2
<=> (n(n+1)(n-1)/4 <= 2^n

So ganz nach dem Motto: wenn a<b, dann ac<bc
a wäre dann "(n(n+1)(n-1))/4"
b wäre "2^n"
c wäre 2

Die andern aus der Mathe-Lerngruppe hat das als die Lösung angesehen und abgeschrieben, ich persönlich hab das Gefühl, dass das zu einfach ist!

10.10.2012, 17:53

BioKai

Auf diesen Beitrag antworten »

2. Nach Indiktionsschritt (IS):

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

dann hat man den Faktor $\begin{eqnarray*} \frac{(n+2)}{2n} \end{eqnarray*}$
und dann bekommt man $\begin{eqnarray*} \frac{4}{n-1} * \frac{(n+2)}{2n} \end{eqnarray*}$ für die rechte Seite der Ungleichung.

Das ist in meinen Augen der richtige Ansatz, aber ich habs zu keinem endgültigen Beweis gebracht, wenns einer von euch packt darf er mir gern helfen smile

smile

Edit(Helferlein): Latexklammern nachgetragen, zweiten Beitrag gleichen Inhalts gelöscht.

10.10.2012, 18:25

BioKai

Auf diesen Beitrag antworten »

3. Ich hab heute einen Mathe-Doktorant getroffen, den Harri (vom Mathe-Vorkurs, falls einer von euch dort war). Er hat ca. ne halbe bis 3/4 Stunde an der Aufgabe rumgerechnet und konnte mir kein Resultat liefern...
Als ich später nochmal zu ihm hingegangen bin um ihm meinen neuen Lösungsansatz zu präsentieren (den 1. hab ich ihm gar nicht gezeigt weil ich davon ausgegangen war, dass er garantiert falsch ist) meinte er, ihm ist eingefallen wie es geht. Leider komm ich aus seinen verwirrenden Aufschrieben nicht ganz draus, aber er hat ungefähr das formuliert:

1. Er sagt man muss hier die Induktion nicht mit n -> n+1 sondern mit n-1 -> n machen, also:

$\begin{eqnarray*} \frac{n(n-1)}{2^{n-1}} \leq \frac{(4)}{n-2} \end{eqnarray*}$

2. Faktor finden:

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

3. Ungleichung aufstellen:

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

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

und jetzt das verwirrende: Aus der Rechten Seite dieser Ungleichung formt er nun:
$\begin{eqnarray*} = \frac{4}{n-1} * \frac{(\frac{n+1}{n-2})}{2} = \frac{n-2+3}{n-2} = 1 + \frac{3}{n-2} \leq 1 \end{eqnarray*}$

...und dann sagt er: "Es ist sogar kleiner als 1..."

Gerne eure Meinungen zu den 3 Lösungsansätzen!

10.10.2012, 19:57

Gastt

Auf diesen Beitrag antworten »

Zitat:

Original von BioKai
Das ist in meinen Augen der richtige Ansatz, aber ich habs zu keinem endgültigen Beweis gebracht, wenns einer von euch packt darf er mir gern helfen smile

smile

Yep, damit kanns weitergehen.

Du darfst ja voraussetzen, dass

$\begin{eqnarray*} \frac{n(n+1)}{2^n}<\frac 4{n-1}. \end{eqnarray*}$

Und Du willst im IS daraus folgern, dass

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

Um dies zu tun hast bereits gesehen, dass

$\begin{eqnarray*} \frac{(n+1)(n+2)}{2^{n+1}}=\frac{n(n+1)}{2^n}\cdot\frac{n+2}{2n}\stackrel{IV}{<}\frac 4{n-1}\cdot\frac{n+2}{2n}=\frac 4n\cdot \frac{n+2}{2(n-1)} \end{eqnarray*}$

Jetzt fehlt also nur noch die Gewissheit darüber ob vielleicht

$\begin{eqnarray*} \frac{n+2}{2(n-1)}\leq1 \end{eqnarray*}$

gilt, denn damit wäre der Induktionsschritt komplett - nicht wahr?!?

(Bedenke das laut Vor. $\begin{eqnarray*} n\geq 4 \end{eqnarray*}$ )

10.10.2012, 21:50

BioKai

Auf diesen Beitrag antworten »

Yeah Mann! Du bist ein Genie!

Danke!!

11.10.2012, 02:38

krypt0n11

Auf diesen Beitrag antworten »

WOW!!!
Das ist wirklich genial!
Aber da wäre ich nie im Leben drauf gekommen -.-
Vielen Dank ihr beiden Big Laugh

Big Laugh

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »