Fragen zu [Workshop]-[Vollständige Induktion] - Seite 3

22.09.2005, 19:37

JochenX

kann es sein, dass du uns einige details verschweigst?
so ist es ziemlich zusammenhanglos

poste mal den vollständigen beweis!

22.09.2005, 20:47

Mathespezialschüler

Auf diesen Beitrag antworten »

@LOED
Das ist ein Fragenthread zu einem Workshop und hier geht es wohl grad um das.
@Cosmo
Du willst $\begin{eqnarray*} 2^{n+1}>(n+1)^2 \end{eqnarray*}$ beweisen. Du hast schon $\begin{eqnarray*} 2^{n+1}>2n^2 \end{eqnarray*}$ und wenn jetzt $\begin{eqnarray*} 2n^2>(n+1)^2 \end{eqnarray*}$ ist, dann folgt

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

also die zu beweisende Aussage. Dass das erst gezeigt werden soll, ist richtig, aber es wird hier äquivalent umgeformt. Du weißt doch, was das bedeutet oder?

Gruß MSS

22.09.2005, 23:29

Cosmo

Auf diesen Beitrag antworten »

Äh, ja, so ungefähr *hehe*

Also normaler Weise ist es bei Induktion doch so, dass ich die linke Seite so umwandel, dass ich die IV einsetzen kann.
Und mit der IV und dem was da noch über geblieben ist, wurstel ich dann so lange rum, bis ich die rechte Seite der IV habe wo statt n allerdings nun n+1 steht.

Aber das funktioniert hier ja irgendwie nicht.

Um bei diesem Beispiel zu bleiben:

Ich habe im IS $\begin{eqnarray*} 2^{n+1} \end{eqnarray*}$
Das wandel ich um, so dass ich die IV einsetzen kann: $\begin{eqnarray*} 2 \cdot 2^n \end{eqnarray*}$

Nur darf ich jetzt ja nicht 2n² nehmen und rumwursteln bis da (n+1)² steht. (was offensichtlich ja auch nicht gehen würde)

Also mal sehen ob ich das verstehe.
Ich habe $\begin{eqnarray*} 2^{n+1} > (n+1)^2 \end{eqnarray*}$
Und $\begin{eqnarray*} 2^n \end{eqnarray*}$ ist größer als n² laut IV

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

Soweit habe ich es verstanden.

Nur habe ich immer noch das Problem, dass von Anfang an auf der rechten Seite der Ungleichung "(n+1)²" steht und darauf soll ich doch selber erst kommen!

Um das mal zu verdeutlichen, was ich an der Sache nicht verstehe.

Ich weiß, dass 4>3

Nun soll ich zeigen, dass 12>7

Also weiß ich, dass 3*4>7 ist

Nun kann ich meine IV (also 4>3) hier einsetzen:

4>3
also ist
3*4>3*3

Woraus ich folgere, dass 3*4>3*3>7 ist.

Hier sieht man, es so oder so, das 12 größer als 7 ist.
Aber nur weil ich noch eingefügt habe, dass 12 größer als 9 ist und 9 größer als 7 habe ich das doch noch nicht gezeigt.
Oder doch ... ??? Moment mal ...

Nee, hab ich nicht. ich sehe zwar, dass 9 > 7 ist, aber genau wie bei 12>7 ist dies nur eine Vermutung.
Und genauso geht es mir bei der echten Induktion da oben auch :-?

(Und ja, ich weiß dass dieses Zahlenbeispiel nicht im entferntesten als Induktion bezeichnet werden kann, aber ich hoffe es macht etwas deutlicher, was an der Sache ich nicht verstehe :-)

23.09.2005, 14:00

Mathespezialschüler

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 2n^2>(n+1)^2 \end{eqnarray*}$ ist aber keine Vermutung, sondern es ist ja wahr für $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ !!! Dass das tatsächlich stimmt, wurde ja durch äquivalente Umformung gezeigt.
Vll verstehst du es ja, wenn ich das ganze nochmal etwas anders aufschreibe (in einer besseren Reihenfolge und mit einer anderen Umformung):
Für alle $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ gilt $\begin{eqnarray*} 2^n>n^2 \end{eqnarray*}$ .
Als Hilfssatz beweisen wir zunächst

$\begin{eqnarray*} 2n^2>(n+1)^2 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ .

Es gilt nämlich für $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ :

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

Also gilt auch $\begin{eqnarray*} 2n^2>(n+1)^2 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$

Jetzt der Beweis für $\begin{eqnarray*} 2^n>n^2 \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ durch Induktion:

IA: $\begin{eqnarray*} n=5 \end{eqnarray*}$ : $\begin{eqnarray*} 2^5=32>25=5^2 \end{eqnarray*}$ ist also wahr.

IV: Es gelte für $\begin{eqnarray*} n \end{eqnarray*}$ : $\begin{eqnarray*} 2^n>n^2 \end{eqnarray*}$

IS: Dann gilt:

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

nach Induktionsvoraussetzung. Nach dem Hilfssatz ist $\begin{eqnarray*} 2n^2>(n+1)^2 \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 5 \end{eqnarray*}$ . Also folgt auch

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

und das war zu beweisen.

Ist es jetzt klarer?

Gruß MSS

23.09.2005, 16:09

Cosmo

Auf diesen Beitrag antworten »

Ja, langsam wird es heller. Aber irgendiwe finde ich das verdammt abstrakt, wenn man mal bedenkt, wie simple die Induktion bei Gleichungen ist.

Eine Sache möchte ich noch mal aufgreifen:
Den Hilfssatz kapier ich nicht.

Zitat:

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

$\begin{eqnarray*} 2n^2=n^2+n^2 \end{eqnarray*}$
Das is klar.

$\begin{eqnarray*} n^2+3n=n^2+2n+n \end{eqnarray*}$
Dies ist auch klar, aber woher kommt das.

Haben wir bei dem Hilfssatz irgendeine IV, die wir einsetzen können? Oder woher kommt das. Alter Schwede, das kann doch nicht so schwer sein?! Unglaublich.
Danke auf jeden Fall schon mal für Deine Bemühungen :-)

23.09.2005, 16:57

Mathespezialschüler

Auf diesen Beitrag antworten »

Das hat jetzt gar nichts mit Induktion zu tun! Man kann auch Sachen über natürliche Zahlen ohne Induktion beweisen! Das sind jetzt einfach ganz normale Rechenregeln. $\begin{eqnarray*} 3n=2n+n \end{eqnarray*}$ ist doch ganz trivial, also nicht zu viel an Induktion denken, sondern auch mal weg von der Induktion zu anderen Beweismöglichkeiten gucken. Augenzwinkern

Gruß MSS

23.09.2005, 19:44

Cosmo

Auf diesen Beitrag antworten »

Ok...

Wie gesagt 3n = 2n+n ist mir wie gesagt klar.

Aber woher kommt das? Nirgends wo sonst kam doch bis jetzt n²+3n vor und es lässt sich doch auch aus nichts umwandeln?! Also wo kommt das her?

23.09.2005, 19:56

Mathespezialschüler

Auf diesen Beitrag antworten »

Ich verstehe absolut nicht, was du meinst. Was mich mir höchstens noch vorstellen könnte, wäre, dass du nicht verstehst, warum

$\begin{eqnarray*} n^2+n^2\geq n^2+3n \end{eqnarray*}$

gilt, richtig? Das gilt, weil wir nach Voraussetzung $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ haben, also (mit $\begin{eqnarray*} n \end{eqnarray*}$ multiplizieren!)

$\begin{eqnarray*} n^2\geq 3n \end{eqnarray*}$

und daraus folgt (auf beiden Seiten $\begin{eqnarray*} +n^2 \end{eqnarray*}$ ):

$\begin{eqnarray*} n^2+n^2\geq n^2+3n \end{eqnarray*}$

Meintest du das? verwirrt

Gruß MSS

24.09.2005, 12:14

Cosmo

Auf diesen Beitrag antworten »

Ja, genau das miente ich, danke :-)

Ich wusste nicht, wie Dud arauf kammst, nun is es einigermaßen klar.

Ich höre jetzt auch gleich auf mit Fragen, nur möchte ich noch mal wissen, wie Du auf n>3 gekommen bist.
Gut, man kann es hier ersehen, aber es geht ja ums Prinzip.

Wenn ich das umforme komme ich auf:

$\begin{eqnarray*} 2n^2\ge n^2+2n+1 \end{eqnarray*}$
$\begin{eqnarray*} n^2\ge 2n+1 \end{eqnarray*}$
$\begin{eqnarray*} n \ge 2+ \frac 1 n \end{eqnarray*}$
Es soll doch aber n>3 also 2+1 nicht 2+1/n rauskommen?!

26.08.2008, 16:24

ajax2leet

Auf diesen Beitrag antworten »

Ein relativ populärer Satz, den man mit vollst. Ind. beweisen kein, ist der "kleine Fermat" (http://de.wikipedia.org/wiki/Kleiner_fermatscher_Satz)

Hier ein Auszug aus meiner Facharbeit:

Der Satz lautet : $\begin{eqnarray*} a^p \equiv a\pmod{p} \end{eqnarray*}$ oder anders $\begin{eqnarray*} p | (a^p - a) \end{eqnarray*}$ (lies: p teilt (a^p -a)

a ist hierbei eine Natürliche Zahl und p eine Primzahl.

Induktionsvorraussetzung: $\begin{eqnarray*} A(n) \Rightarrow A(n+1) \end{eqnarray*}$
$\begin{eqnarray*} \Leftrightarrow n^p \equiv n\pmod{p} \Rightarrow (n+1)^p \equiv (n+1)\pmod{p} \end{eqnarray*}$
oder anders $\begin{eqnarray*} p | (n^p - n) \Rightarrow p | ((n+1)^p - (n+1)) \end{eqnarray*}$

Induktionsanfang:
$\begin{eqnarray*} A(0) \Rightarrow p | (0^p - 0) \end{eqnarray*}$
(Für die Ungläubigen : http://de.wikipedia.org/wiki/Teilbarkeit Augenzwinkern

)

Induktionsschritt:
$\begin{eqnarray*} A(n+1) = (n+1)^p - (n+1) = \sum_{k=0}^{p}{p \choose k } n^{p-k}1^{k}-(n+1) \end{eqnarray*}$ (Binomialsatz)

Nun benutzen wir einen kleinen Trick: Aus der Summe ziehen wir den höchsten und den niedrigsten Summanden heraus. (Also die Summanden mit k=0 und k=n)
$\begin{eqnarray*} (n+1)^p - (n+1) = \sum_{k=1}^{p-1}{p \choose k } n^{p-k}1^{k}-(n+1) + n^p + 1 \end{eqnarray*}$

Nun wird umgeformt
$\begin{eqnarray*} (n+1)^p - (n+1) = n^p - n + \sum_{k=1}^{p-1}{p \choose k } n^{p-k}1^{k} \end{eqnarray*}$

Die Hauptarbeit ist nun getan. Man erkennt, wie A(n+1) aus A(n) hervorgeht.
Nämlich: $\begin{eqnarray*} A(n+1) = A(n) + \sum_{k=1}^{p-1}{p \choose k } n^{p-k}1^{k} \end{eqnarray*}$
Im Induktionsanfang haben wir den Satz für A(0) bewiesen. Nun bleibt zu Zeigen, dass $\begin{eqnarray*} p | \sum_{k=1}^{p-1}{p \choose k } n^{p-k}1^{k} \end{eqnarray*}$

$\begin{eqnarray*} p \choose k \end{eqnarray*}$ ist ja nichts anderes als $\begin{eqnarray*} \frac{p!}{(p-k)!\cdot k!} \end{eqnarray*}$

und $\begin{eqnarray*} p! \end{eqnarray*}$ bedeutet ja $\begin{eqnarray*} 1\cdot 2 \cdot 3 \cdot ... \cdot (p-1) \cdot p \end{eqnarray*}$

Man erkennt also unschwer, dass $\begin{eqnarray*} p | {p \choose k} \end{eqnarray*}$ und somit auch $\begin{eqnarray*} p | \sum_{k=1}^{p-1}{p \choose k } n^{p-k}1^{k} \end{eqnarray*}$

Daraus folgt dann schlussendlich:
$\begin{eqnarray*} p | (n^p - n) \Rightarrow p | ((n+1)^p - (n+1)) \end{eqnarray*}$

q.e.d.

26.08.2008, 16:26

Zizou66

Auf diesen Beitrag antworten »

Achte demnächst darauf, von wann der Thread, auf den du eine Antwort gibst, ist. Hier wird sich der Fragesteller wohl nicht mehr für die Antwort interessieren.

27.08.2008, 11:59

ajax2leet

Auf diesen Beitrag antworten »

Hm, ich hielt das für eine nette Ergänzung zu dem Workshop. Da ich in den Workshop thread nicht posten konnte, hab ichs eben hier rein gepackt.
Wen das Thema interessiert, dem ist es egal, wie alt es ist.

27.08.2008, 12:08

Auf diesen Beitrag antworten »

Sehe ich ähnlich: Das hier ist ja kein spezieller Fragethread, sondern eher eine Art Spielwiese für alle Fragen rund um Induktion. Da sollte man nicht reglementieren, wer wie wo was wann schreiben darf. Augenzwinkern

« vorherige Seite 123

Neue Frage »

Antworten »

Fragen zu [Workshop]-[Vollständige Induktion] - Seite 3

Verwandte Themen