Beweis durch Induktion

07.11.2008, 12:09

imag

Auf diesen Beitrag antworten »

Beweis durch Induktion

Hallo
ich hätte da die aufgabe:
n E N
$\begin{eqnarray*} n!\leqslant(n/2)^n \end{eqnarray*}$
Behauptung: für alle $\begin{eqnarray*} n\geqslant6:n!\leqslant(n/2)^2 \end{eqnarray*}$
Beweis: 1. Induktionsanfang: n=6
2. Induktionsschritt: k->k+1 $\begin{eqnarray*} (k\geqslant6) \end{eqnarray*}$
$\begin{eqnarray*} (k+1)!\leqslant(k+1durch2)hoch k+1 \end{eqnarray*}$
Kann mir da jemand weiterhelfen wie ich geschickt an den beweis rangehe und bzw wie der funktioniert?
Danke!!

07.11.2008, 12:11

tigerbine

Auf diesen Beitrag antworten »

Vielleicht nun mal etwas optisch ansprechender? Augenzwinkern

Augenzwinkern

Wie kann man Formeln schreiben?

07.11.2008, 12:17

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion

Zitat:

Original von imag
$\begin{eqnarray*} (k+1)!\leqslant(k+1durch2)hoch k+1 \end{eqnarray*}$

Wollen wir nicht lieber bei der Variable n bleiben?

$\begin{eqnarray*} (n+1)! \leq \left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$

Auch hier fängt man mit der linken Seite an, formt so um, daß man die Induktionsannahme verwenden kann, und schaut dann zu, daß man auf die rechte Seite kommt.

07.11.2008, 13:20

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
genau das ist mein problem. hab das schon auf ganz viele arten versucht umzuformen, aber irgendwie kommt nie was sinnvolles dabie rüber! hat vllt jemand einen tipp auf was ich mich hier beziehen kann beim umformen?

07.11.2008, 13:23

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Der erste Schritt wäre doch erstmal (n+1)! = n! * (n+1) zu schreiben und die Induktionsannahme einzubauen.

EDIT: Okay, ich gebe zu, der Beweis ist etwa fies. Also noch ein Tipp:

Wegen der Bernoullischen Ungleichung gilt: $\begin{eqnarray*} \left(1 + \frac 1 n \right)^n \geq 1 + n \cdot \frac 1 n = 2 \end{eqnarray*}$

Nun geht's los:

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

Jetzt etwas zusammenfassen und die 2 mit der Bernoullischen Ungleichung nach oben abschätzen. Fertig.

07.11.2008, 16:02

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Habe die rechte seite jetzt mal umgeformt: das sinnvollste auf das ich komme ist $\begin{eqnarray*} (\frac{n}{2})^n*(n+1) \end{eqnarray*}$
weiß jetzt m´nicht so recht was ich damit anfangen kann. eigentlich müsste ich doch auf die Form: $\begin{eqnarray*} (1+\frac{1}{n})^n \end{eqnarray*}$ kommen oder? aber wie??

Anzeige

07.11.2008, 16:04

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Moment blödsinn. Ich habe ja genau das wie am anfang. also im kreis gerechnet! muss ich es nochmal anders versuchen.

07.11.2008, 16:06

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Da stehen 5 Faktoren. Die ersten beiden kannst du zusammenfassen. Ebenso die nächsten beiden. Den letzten Faktor wie schon gesagt nach oben abschätzen.

07.11.2008, 16:58

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Das habe ich gemacht.
$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \end{eqnarray*}$
das sieht aber noch ziemlich anders aus als das, das in der Formel steht.
Kann da jetzt nicht viel mehr mit anfangen.
das n+1 muss in die potenz.

EDIT: Latex verbessert (klarsoweit)

07.11.2008, 19:02

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
hab noch was vergessen: die klammern fehlen. hat irgendwie nicht funktioniert. die brüche sollen jeweils in klammern stehen!

07.11.2008, 20:48

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Wie ich schon sagte, mußt du die 2 auch nach oben abschätzen:

Zitat:

Original von klarsoweit
Wegen der Bernoullischen Ungleichung gilt: $\begin{eqnarray*} \left(1 + \frac 1 n \right)^n \geq 1 + n \cdot \frac 1 n = 2 \end{eqnarray*}$

08.11.2008, 13:42

imag

Auf diesen Beitrag antworten »

ok dann habe ich dann:
$\begin{eqnarray*} (\frac{n}{n+1})^n\cdot(\frac{n+1}{2})^n+1\cdot2\geqslant n!(n+1) \end{eqnarray*}$
das n+1 muss komplett in dei potenz. klappt irgendwie nicht.
kann ich jetzt sagen dass wegen der bernoullischen ungleichung die 2 höchstens (1+1/n)hoch n groß ist und deswegen die gleichnung stimmt? aber das reicht doch nicht oder? was meinst du genau mit abschätzen?

08.11.2008, 14:31

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Ach je, ach je. Aus einem "mal 2" machst du ein "plus 2" und hängst für mich nicht nach vollziehbar ein ">= n! * (n+1) hinten dran. unglücklich

unglücklich

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

08.11.2008, 14:44

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
ich hab doch geschrieben das das keine + 2 ist sondern ne mal 2. die +1 ist mir nur aus der potenz runtergerutscht. ich glaub das war ei missverständnis.
und das andere ist genau die gleiche gleichung die du mir gesendet hast nur umgeformt bzw zusammengefasst. oder etwa nicht?
aber wie passt deine gleichung jetzt noch zu der ersten? das verstehe ich nicht.

08.11.2008, 15:22

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion

Zitat:

Original von imag
ich hab doch geschrieben das das keine + 2 ist sondern ne mal 2. die +1 ist mir nur aus der potenz runtergerutscht. ich glaub das war ei missverständnis.

Ahh, ok. Hatte ich überlesen. Ich dachte, mittlerweile wüßtest du, wie man n+1 in den Exponenten schreibt. Hatte ja schon deswegen deinen vorigen Beitrag korrigiert.

Was du aus der Bernoullischen Ungleichung gemacht hast, ist mir immer noch nicht klar. Ich nutze schlicht und ergreifend dieses:

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

08.11.2008, 15:49

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
ich hatte garnichts aus der bernoullischen ungleichung gemacht. ich habe einfach nur meinen induktionsschritt sozusagen zusammengefasst.

08.11.2008, 16:00

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Wie gesagt, ich habe es nicht verstanden.

08.11.2008, 16:36

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Nun geht's los:

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

das hattest du mir doch gesendet. und ich habe dann so umgeformt:

[quote]Original von imag

$\begin{eqnarray*} (\frac{n}{n+1})^n\cdot(\frac{n+1}{2})^n+1\cdot2\geqslant n!(n+1) \end{eqnarray*}$

und ich weiß dass, nach der bernoullischen ungleichung:

$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \leq \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot \left( \frac{n+1}{n} \right)^n = \left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$
und jetzt hänge ich fest. ich finde da keinen zusammenhang. ich glaub ich stehe auf dem schlauch! was sagt mir das denn?

08.11.2008, 16:45

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Ahh, jetzt weiß ich, was du meintest. Im Gesamtblick haben wir jetzt:

$\begin{eqnarray*} (n+1)! \leq \left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$

Und genau das war das, was im Induktionsschritt zu zeigen ist.

08.11.2008, 16:49

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
genau, also stimmte das doch oder?
war gerade total verwirrt und dachte jetzt wüsste ich garnichts mehr!
Weiß nur jetzt nicht so recht was ich mit den aussagen anfangen kann. das ist die ganze zeit schon mein problem.

08.11.2008, 16:53

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Also noch mal kurz zum Anfang der Geschichte. Wir wollten zeigen, daß gilt:

$\begin{eqnarray*} n! \leq \left( \frac{n}{2} \right)^{n} \end{eqnarray*}$

Im Induktionsschritt, wird obiges als Induktionsvoraussetzung genommen und es ist dann zu zeigen, daß gilt:

$\begin{eqnarray*} (n+1)! \leq \left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$

Joo, und das haben wir ja jetzt. smile

smile

PS: macht ihr sowas an einer Schule?

08.11.2008, 17:02

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
hab gerade angefangen zu studieren und hab vorher in der schule nicht viele beweise machen müssen deswegen fällt mir das schwer. hinzukommt noch dass ich auch hier im forum neu bin und zuerst mal rausfinden musste wie das funktioniert und so. deswegen wahrscheinlich auch die missverstände.

08.11.2008, 17:04

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
OK. Dann schiebe ich das mal in die Hochschulmathe. Aber der Beweis ist jetzt klar?

08.11.2008, 17:23

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
also so halb. bin ich da jetzt schon soweit fertig? hab das nicht ganz verstanden wie ich die "2 nach oben abschätzen" soll?

08.11.2008, 17:38

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Wir verwenden die Gültigkeit der Ungleichung $\begin{eqnarray*} 2 \leq \left( \frac{n+1}{n}\right)^{n} \end{eqnarray*}$ und setzen statt der 2 den Term auf der rechten Seite ein.

08.11.2008, 17:53

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
welchen term meinst du jetzt?
n!(n+1)?

09.11.2008, 12:32

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Statt 2 setze ich $\begin{eqnarray*} \left( \frac{n+1}{n}\right)^{n} \end{eqnarray*}$ ein. Dadurch wird der Term, in dem die 2 drin steckt, nur noch größer.

09.11.2008, 14:40

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
das ist jetzt meine bernoulische ungleichung:
$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$
und ich setze (unter verwendung der bernoullischen ungleichung) anstatt der 2 auf der linken seite
$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \end{eqnarray*}$ ein.
dann habe ich:
$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot \left( \frac{n}{n+1} \right)^n\leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$
und der term: $\begin{eqnarray*} \left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$ wird so noch größer.
ist das jetzt mein beweis, dass $\begin{eqnarray*} (n+1)!\leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$ stimmt?
dann müsste ja eigentlich $\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot \left( \frac{n}{n+1} \right)^n=(n+1)! \end{eqnarray*}$ sein. sehe ich das so richtig? hoffe es sind diesmal keine tippfehler drin. Augenzwinkern

Augenzwinkern

09.11.2008, 15:10

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion

Zitat:

Original von imag
das ist jetzt meine bernoulische ungleichung:
$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$

Nein. Das ist die Bernoullische Ungleichung:
$\begin{eqnarray*} 2 \leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$

Genau das und nichts anderes und nichts anderes habe ich in meinen obigen Beiträgen geschrieben. Ich frage mich, ob du die liest.

Du setzt die rechte Seite der Bernoullische Ungleichung an dieser Stelle:

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

für die 2 ein. Also gilt dann:

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

09.11.2008, 16:03

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
ohh sry hatte da scheinbar was falsch verstanden. natürlich llese ich deine beiträge.

$\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \leq \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot \left( \frac{n+1}{n} \right)^n \end{eqnarray*}$
gut soweit bin ich jetzt:
und die rechte seite kann ich doch zusammenfassen und habe dann:
$\begin{eqnarray*} \left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$ auf dieser seite.
das ist ja das was ich will.
und damit bin ich doch fertig oder?weil wenn
$\begin{eqnarray*} n!(n+1)\leq\left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \end{eqnarray*}$ ist und $\begin{eqnarray*} \left( \frac{n}{n+1} \right)^n \cdot \left( \frac{n+1}{2} \right)^{n+1} \cdot 2 \leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$ dann ist $\begin{eqnarray*} n!(n+1)\leq\left( \frac{n+1}{2} \right)^{n+1} \end{eqnarray*}$
oder?

09.11.2008, 20:03

klarsoweit

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Ja, so ist es.

10.11.2008, 20:48

imag

Auf diesen Beitrag antworten »

RE: Beweis durch Induktion
Vielen Dank für deine Hilfe!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »