[WS] Vollständige Induktion

Neue Frage »

Deakandy Auf diesen Beitrag antworten »
[WS] Vollständige Induktion
Da ich mich nun auch mit dem Formeleditor beschäftigt habe, werde ich demnächst mal ein oder zwei Induktionsaufgaben erklären, da diese meist sehr umfangreich sind und nicht so schnell beantwortet werden können; ohne viel Aufwand.
Als erstes Beispiel füge ich den Satz von C.F.Gauss (1777-1855) ein, den er als Schüler bewiesen hat, als er die Zahlen von 1 bis 100 addieren sollte
Als zweites Beispiel wähle ich einfaches aus dem Bereich der Ungleichungen
Als drittes Beispiel wähle ich eine Ungleichung mit einem Binomialkoeffizienten

Bei Fehlern bitte nicht direkt den Kopf abhacken sondern lieber mal ne pn schicken.
Gruß Andy

Nachtrag von Jama: Fragen, Kritik und Wünsche zu diesem Workshop bitte hierhin: http://matheboard.de/thread.php?threadid=1550 .
Deakandy Auf diesen Beitrag antworten »
Vollständige Induktion Summe und Bruch
1. Beispiel
Für alle gilt:

Beweis: Wir zeigen die Aussage durch Induktion nach n
Induktionsanfang (IA): Man zeige, dass n=1 gilt

Induktionsvorraussetzung (IV): Es gelte für ein
Induktionsschluss (IS): Man schließe von n auf n+1:
Das heißt man hat zu zeigen, das folgendes gilt:

Nun geht man wie folgt vor:

In diesem Schritt holt man lediglich den letzten Summanden raus.
Nun kann man die Induktionsvorraussetzung anwenden
Man setzt für die Summe
genau das ein, was aus der Voraussetzung gilt und zwar
Eingesetzt ergibt sich dann folgender Term:



Diese Summe bringt man geschickt auf einen Bruch durch Erweitern







Und genau das war zu zeigen.
Man hat nun genau die Form, wie sie unter dem Induktionsschluss stehen hat.
Die Behauptung ist dem Prinzip der vollständigen Induktion bewiesen. q.e.d.
 
 
Deakandy Auf diesen Beitrag antworten »
Übungen zur Vollständigen Induktion
Übungen zu diesem Beispiel
Ein anderer Satz, der analog zum ersten Typen bewiesen werden kann, ist die Geometrische Summenformel
Für und jede reelle (komplexe) Zahl gilt:


Wer sich mit dem Binomialkoeffizienten auskennt, für den wid auch folgende Aufgabe kein Problem sein
Deakandy Auf diesen Beitrag antworten »
RE: Vollständige Induktion
2. Beispiel
Für alle , gilt:

IA: Für n=5 gilt
IV:Es gelte für ein
IS:
Es ist also zu zeigen, dass

beginnt man auf der linken Seite so erhält man

nun kann man für per induktionsvorraussetzung einsetzen



Dies gilt weil
Man beachte hier, dass die Ausage auch für n=1 gilt.
Die Behauptung wurde per Induktionsbeweis bewiesen.
Eine eventuell elegantere Lösung, die weniger Zweifel mit sich bringt.

Zitat:
Original von SirJective
Ich formuliere DeakAndys Beweis mal so um, dass klar wird, was er gemeint hat.

Für alle gilt:
IA: Für n=5 gilt
IV:Es gelte für ein die Ungleichung .
IS:
Es ist also zu zeigen, dass .
Durch Umformung der linken Seite erhält man die äquivalente Aussage .
Die folgt mit der Induktionsvorraussetzung aus der (noch zu zeigenden!) Aussage .
In letzterer Ungleichung beide Seiten etwas umgeformt erhält man die äquivalente Ungleichung .

Diese ist für erfüllt, weil offensichtlich ist.

Was DeakAndy hier gemacht hat, ist: Er hat an jeder Stelle ein hinreichende Bedingung für die Erfülltheit der vorigen Aussage angegeben, d.h. er sagt: Wenn die zweite Aussage gilt, dann gilt auch die erste.

Leopold: Dein "Beweis" hat mit diesem Schema gar nichts zu tun, da du sagst: Wenn die erste Aussage gilt, dann gilt auch die zweite. Und dabei wagst du es *g*, mit 0 zu multiplizieren.

Wenn du nun die Reihenfolge der Argumentation in DeakAndys Beweis umdrehst, erhältst du einen "sauberen" Beweis, den jeder nachvollziehen kann.

Gruss,
SirJective


Es gibt sicher noch eine andere Methode, in der man nicht abschätzen muss.
Dazu ein anderes Beispiel, das ebenfalls aus einer Ungleichung besteht.
Deakandy Auf diesen Beitrag antworten »
Vollständige Induktion mit einer Binomialkoeffizient und Ungleichung
3.Beispiel
Es sei folgende Ungleichung zu beweisen:



IA: Für n=1 ist

(w) (edit: hier verbessert, jochen)

IV: Es gelte für ein
IS:
zu zeigen


Nun gehe ich einmal von der rechten Seite aus:



ist wenn man genau hinsieht der ausgeschrieben Binomialkoeffizient von
Also kann man die Induktionsvoraussetzung einsetzen
Man erhält








Naja und wem das noch nicht offensichtlich genug ist kann ja noch ein Weilchen kürzen.

(w)
(Man kann sicherlich vorher schon geeigneter umrechnen)
Die behauptung ist damit per Induktion bewiesen. q.e.d.
Deakandy Auf diesen Beitrag antworten »
Übung zu Vollständige Induktion mit einer Binomialkoeffizient und Ungleichung
Darauf aufbauend könnte man die Ergänzung

per Induktion beweisen.

Ebenfalls recht einfach zu beweisen ist die folgende Ungleichung
johko Auf diesen Beitrag antworten »

Allgemeiner TIPP, der bisher den Durchsschnittsschülern immer schnell zur Einsicht verholfen hat - anhand Beispiel 1:

1)Schreibe die erste Zeile und das Ergebnis nach Anweisung(siehe dort)
2) Mach dir damit folgendes Schema




= ...
= ...
= ...
=

3)Arbeite dich "von oben" und "von unten" durch Umformen soweit in die Mitte vor, bis du zwei gleiche Zeilen erkennst.

Etwa so:


=

=

=
=
=die obere und untere Zeile sind gleich
=

=

In der Schule müssen nämlich Vollst. Ind. nicht ERFUNDEN, sondern nur NACHVOLLZOGEN werden
paukergruss Johko
(es funzt mit dem Formeleditor!!!*freu*)
Deakandy Auf diesen Beitrag antworten »
Induktionsaufgabe mit 2 Summen
Eine weitere schöne Induktionsaufgabe ist die folgende:

IA: Für n=1 gilt

IV: Es gelte für ein
IS: Man zeige


Nun setzt man die Induktionvoraussetzung ein
. Nun ein kleiner Trick, indem man den Satz von Gauß anwendet
Nun hat man eine Gleichung mit einer Unbekannten und müsste diese wieder auf die Form bringen.
Dies scheint jedoch nicht direkt ins Augenlicht zu fallen und deshalb räumt man das Feld von hinten auf und versucht auf die in Anführungsstriche gesetzte Form zu bringen.


Ich habe die Zwischenschritte mal nicht hingeschrieben, da es sich lediglich um algebraische Umformungen handelt und diese von jedem selber nachgerechnet werden können.

Die behauptung folgt per induktionsprinzip q.e.d.
Deakandy Auf diesen Beitrag antworten »
RE: Induktionsaufgabe mit 2 Summen
Als ich doch letztens noch mal meine Sachen durchgeblättert habe, ist mir noch eine nette Aufgabe in den Sinn gekommen, die ich euch nicht vorenthalten möchte, da da doch ein bisschen hintersteckt smile
Jeder kennt die binomische Formel für n=1,2,3 wenn die allgemeine Form (a+b)^n ist.
Nun zur Aufgabe

Wir beweisen die Aussage durch Induktion nach n
(IA) Im Fall n=0 gilt

(IS) Die obige Formel gelte für ein .
Durch Multipliaktion mit (a+b) folgt daraus


Nun etwas Neues in diesem Workshop, eine Indexverschiebung.
Man ersetzt








Und genau das war zu zeigen...ein schöner Beweis, der eine Menge anderer Kenntnisse abverlangt...Fragen dazu bitte in den dazu erstellten Fragethread...
AD Auf diesen Beitrag antworten »
RE: Induktionsaufgabe mit 2 Summen
Angeregt durch einen anderen Thread zu Vollständiger Induktion möchte ich hier im Workshop noch folgendes Grundsätzliches zum Thema beitragen:


Für die Schulbeispiele mag die Sichtweise (oder meinetwegen auch ) ausreichen, aber das Prinzip der Vollständigen Induktion ist viel mächtiger:

Ist die zu beweisende Aussage, die für alle gelten soll, dann kann man das Induktionsprinzip auch so formulieren:

1.Induktionsanfang: Zeige .

2.Induktionsschritt: Für zeige. Dabei darf die Richtigkeit von für alle mit benutzt werden, d.h., nicht nur für .

Einige Sachen lassen sich nur so richtig knacken.

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

Eine zweiter Tipp: Manchmal lohnt es sich, eine schärfere Aussage als die geforderte zu beweisen. Im ersten Moment erscheint das widersinnig, aber auf den zweiten Blick nicht mehr: Mit einer schärferen Aussage kann man ja im Induktionsschritt auch mehr voraussetzen!

Beispiel: Man weise



für alle natürlichen Zahlen durch Vollständige Induktion nach.

Ihr könnt es mal direkt mit V.I. probieren, und daran verzweifeln... Augenzwinkern

Die schärfere Aussage

,

aus der die ursprüngliche Aussage offenbar folgt, lässt sich dagegen ohne größere Schwierigkeiten nachweisen. smile
dast Auf diesen Beitrag antworten »
Induktionsbeweis aus dem Gebiet der Softwareentwicklung
Hallo Leute,

wenn es jemanden interessiert, einen netten Induktionsbeweis aus dem Gebiet der Softwareentwicklung findet ihr unter folgendem Link:

http://www.hh-system.com/danielstrigl/infstud/guess.pdf

MFG Daniel.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »