vollständige Induktion

Neue Frage »

Manix Auf diesen Beitrag antworten »
vollständige Induktion
Geg. ist die Fkt. 2^n>=n^2

bekomm die Induktion bei der Ungleichung nicht auf die Reihe. Verstehs wohl noch nicht so ganz, kann mir jemand helfen. Vielen Dank.
spoonful Auf diesen Beitrag antworten »

hi,

bist du dir sicher, dass deine funktion so stimmt? denn wenn ich n = 3 einsetze bekomme ich 8 >= 9 und das kann ja nicht sein, oder? verwirrt
ich gehe doch davon aus, dass 2^n "2 hoch n" heisst.
 
 
Deakandy Auf diesen Beitrag antworten »
RE: vollständige Induktion
Ja kann ich
geh mal in analysis und dann ist da ein Thema namens vollständige induktion...muss ja mal wieder werbung für mich machen Augenzwinkern

EDIT @ Spoonfool
Es muss ja nicht immer für alle Gleider definiert sein...
kommt oft vor, dass es für 1 geilt,.., dann für 2,3,4 nicht und wieder ab 5
Manix Auf diesen Beitrag antworten »

@ spoonful ja so ist die Aufgabe richtig gestellt.
Induktionsschluß ist nur für n=3,4.... möglich aber wie man drauf kommt ist mir ein Rätsel
Marcyman Auf diesen Beitrag antworten »

Im Induktionsbeweis musst du zeigen:

2^(k+1) >= (k+1)^2 <=> 2^k + 2^k >= k^2 + 2k + 1

Laut Induktionsvoraussetzung ist 2^k >= k^2, damit reduziert sich das Problem also darauf, dass du zeigen musst, 2^k >= 2k +1. Das geht auch ziemlich schnell mit voll. Ind. . Ist zumindest eine Möglichkeit.
Deakandy Auf diesen Beitrag antworten »

ohne Worte ne...
Zitat:
Original von Deakandy
2.Beispiel
Für alle n€|N, gilt:

IA: Für n=5 gilt
IV:Es gelte für ein
IS: n|--> n+1
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.

Es gibt sicher noch eine andere Methode, in der man nicht abschätzen muss.
Dazu ein anderes Beispiel, das ebenfalls aus einer Ungleichung besteht.
Marcyman Auf diesen Beitrag antworten »

Soweit ich das sehe, ist mein Lösungsweg auch berechtigt... wo liegt das Problem?
Irrlicht Auf diesen Beitrag antworten »

Marcymans Lösungsidee ist völlig korrekt.

Deakandys Beweis sieht erstmal auch korrekt aus, aber ich finds beim Indukionsschritt ziemlich undurchsichtig, weil er mit der Induktionsbehauptung anfängt und sich zurückhangelt zu einer wahren Aussage. Man muss den Beweis halt von unten nach oben lesen.
Deakandy Auf diesen Beitrag antworten »

Weder Kritik an Marcyman noch an Irrlicht...
Ich habe mich lediglich darüber aufgeregt, dass der Autor sich nicht die Mühe gemacht hat den Workshop aufzusuchen,..., obwohl drauf hingewiesen...
Zum Beweis...ich denke, es gibt soviele Methoden,..., da kann man sich schonmal eine aussuchen...
Irrlicht Auf diesen Beitrag antworten »

Ah, *g*, ich hab das "ne" oben falsch interpretiert. Sörry. Augenzwinkern
Deakandy Auf diesen Beitrag antworten »

Dafür kann man ja nachfragen...
Gruß Andy
und alles ist wieder in ordnung smile
Wer hilft, dem werde ich nix böses Wollen,.., und wenn sich malein Fehlerchen einschleciht, dann kann man es zusammen verbessern ...
WebFritzi Auf diesen Beitrag antworten »

Der Beweis von Deakandy ist falsch!!! Man kann da eben nicht n^2 für 2^n einsetzen.
Leopold Auf diesen Beitrag antworten »

Ich halte Deakandys Beweis auch für falsch. Man darf einen Beweis nicht mit der Behauptung anfangen. Allerdings ließe sich der Beweis retten, wenn man ihn, wie Irrlicht schon ausgeführt hat, von unten nach oben zusammenbaut. Dieser Arbeit müßte man sich jetzt noch unterziehen!

Ich schlage im Induktionsschritt das Folgende vor (beim ersten Größerzeichen wird die Induktionsannahme, beim Größer-Gleich-Zeichen wird n>4 verwendet):

Deakandy Auf diesen Beitrag antworten »

Wieso ist der falsch?
Naja ich finde der ist richtig...
Aufgebaut wie alle anderen auch smile
Irrlicht Auf diesen Beitrag antworten »

Dein Beweis ist an sich nicht falsch, denn du behauptest an der Stelle "dies gilt weil" ja nur ein und keinen . Nur schreibt man Beweise üblicherweise so, dass zumindest eine durchgängige -Kette (wenn schon keine -Kette) von oben nach unten geht und nicht umgekehrt.
Leopold Auf diesen Beitrag antworten »

"Alle Zahlen sind einander gleich, d.h. es gibt nur eine Zahl."

Ich hoffe, es leuchtet jedem ein, daß der Beweis dieser Behauptung die Mathematik enorm vereinfacht. Schülerschweiß und Schülertränen gehören von jetzt ab der Vergangenheit an!

Beweis:

x=y |-y
x-y=0 |·0
0=0

q.e.d
SirJective Auf diesen Beitrag antworten »

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: n|--> n+1
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
Leopold Auf diesen Beitrag antworten »

@ Sir Jective
Doch, mein Beweis hat durchaus etwas mit Deakandys Vorgehen zu tun. Nur ist bei meinem Vorgehen offensichtlich, daß es unsinnig ist, während Deakandy sein fehlerhaftes logisches Schließen geschickt tarnt. Dein Beweis ist ja auch in Ordnung, aber das wäre Deakandys Aufgabe gewesen, die richtige Reihenfolge der Argumente herzustellen und sie mit entsprechenden Kommentaren (z.B. "... erhält man die äquivalente Aussage...") zu versehen.
Mathematisches Beweisen ist eben gerade nicht Formelrechnen, sondern Formeln/Aussagen in die richtige Reihenfolge bringen und, wenn man einmal von der Implikationsrichtung abweicht, gegebenenfalls erklärende Kommentare anzubringen. Dazu muß man die deutsche Sprache benutzen. Symbolrechnen reicht nicht!
Irrlicht Auf diesen Beitrag antworten »

Wenn jemand beweisen soll "" und mir als Beweis die Folgerung "" angibt, dann ist es korrekt. Da sind wir uns einig. DeakAndys einziger Fehler in seinem Beweis ist, nicht zu sagen, welche Schlussfolgerungsrichtung er beim Anwenden der Induktionsvoraussetzung geht.

Zum Beweisen reicht prinzipiell Symbolschreibweise völlig aus. Es ist möglicherweise komplizierter, aber alle sprachlichen Ausdrücke sind nur Formulierungen mathematischer Begriffe, die prinzipiell auf logische und mengentheoretische Formeln zurückgeführt werden können.

Z.B. kann man DeakAndys Beweis (in SirJectives Formulierung) ganz ohne Verwendung von deutschen Wörtern (oder einer anderen natürlichen Sprache) führen, allein unter Verwendung logischer und mathematischer Formelzeichen.
Irrlicht Auf diesen Beitrag antworten »

Hier noch der Beweis ganz ohne Worte:















Damit ist der Beweis erbracht. :)

PS: Sorry für das Doppelpost.
Leopold Auf diesen Beitrag antworten »

Entsetzlich! Mir schaudert!
Möglicherweise ist das richtig, was du da schreibst! Aber wer außer dem Verfasser kämpft sich durch einen solchen Beweis hindurch?

Ich habe hier noch einmal einen Beweis zum Nachdenken. Eigentlich gehört das nicht mehr zum Thema "Vollständige Induktion". Aber da sind wir ja sowieso davon abgekommen.

Es soll die Identität



nachgewiesen werden. Dazu formen wir um, indem wir zunächst in die dritte Potenz erheben und zusammenfassen:




Mittels (1) kann man bei (2) weiterrechnen:




Damit ist die Identität bewiesen.


aus: A.G.Konforowitsch, Logischen Katastrophen auf der Spur, Fachbuchverlag Leipzig
WebFritzi Auf diesen Beitrag antworten »

Ich finde den Beweis von Irrlicht auch schrecklich. Es ist nicht immer gut, sich nur mit Formeln bzw. mathematischen Zeichen auszudrücken. Dies kann zu Unverständnis bei anderen und auch nach einiger Zeit bei sich selber führen. Ich studiere Mathematik im 13. Semester und weiß, wovon ich rede...
Irrlicht Auf diesen Beitrag antworten »

Oh, dann bist du ja ein Semester über mir. Gott Der Beweis ist richtig und ich finde sowas auch schrecklich. *g* Er sollte ja auch nur demonstrieren, dass man für einen mathematischen Beweis allein mit der mathematischen Formelsprache auskommt.
Soll der Beweis für den Leser leicht nachvollziehbar werden (z.B. in einer Uebungsaufgabe oder in einer Diplomarbeit), empfiehlt sich soetwas wie da oben natürlich nicht. Kein Prof würde sich sowas durchlesen. :P

@Leo
Sowas wie der "Beweis" in deinem letzten Post krieg ich auf fast jedem Übungsblatt der unteren Semester zu korrigieren. Aber nicht nur da... Auch die 5.Semestler haben das letztes Semester bei mir abgegeben und noch Schlimmeres.
So eine Rechnung ist vielleicht ein Hinweis, dass da was beweisbares dran ist. Augenzwinkern

Da ja der ursprüngliche von DeakAndy gegebene Beweis aus dem Workshop stammt, habe ich um Korrektur im entsprechenden Workshop gebeten.
Blind_Zyklop Auf diesen Beitrag antworten »

hallo,
also nachdem ich mit die Vollständige Induktion in
ner kalten nacht beigebrachte hatte und überglücklich
war, dass sie bei allen Beispielaufgaben einschließlich
des 2^n > n^2 für n > 4 funktionierte. Das war auch nich das
Problem! Aber:!!

für n = 1 ist 2^n = 2 und n^2 =1
somit wäre für n = 1 der Induktionsschritt gegeben
und die induktion lässt sich wie bei der annahme von n>4
trotzdem vollziehen (ich hoff das kriegt man noch hin)

Und jetzt meine mich quälende frage: Wie kann man
sowas als Beweisverfahren verwenden wenn man damit
beweisen kann dass z.b. 2^3>3^2 ist (8>9).

Gruß, Cyclop
Irrlicht Auf diesen Beitrag antworten »

Zitat:
für n = 1 ist 2^n = 2 und n^2 =1
somit wäre für n = 1 der Induktionsschritt gegeben
und die induktion lässt sich wie bei der annahme von n>4
trotzdem vollziehen (ich hoff das kriegt man noch hin)


Eben nicht. Um den Induktionsschritt durchzuführen, benötigt man, dass n grösser gleich 3 ist.
Mathespezialschüler Auf diesen Beitrag antworten »

Zitat:
Original von Irrlicht
Zitat:
für n = 1 ist 2^n = 2 und n^2 =1
somit wäre für n = 1 der Induktionsschritt gegeben
und die induktion lässt sich wie bei der annahme von n>4
trotzdem vollziehen (ich hoff das kriegt man noch hin)


Eben nicht. Um den Induktionsschritt durchzuführen, benötigt man, dass n grösser gleich 3 ist.


Also eigentlich habe ich ja keine Ahnung, was ihr hier redet, aber bei n grösser gleich 3 hättest du ja auch 3 mit drin. Und dann wäre wieder 8>9. Meintest du jetzt n größer 3 bzw. n größer gleich 4?? Ansonsten wär das für mich irgendwie sinnlos. verwirrt
WebFritzi Auf diesen Beitrag antworten »

Ja, meinte er.
Blind_Zyklop Auf diesen Beitrag antworten »

hi irrlicht,

du meintest für die induktion müsste n > 3 oder größer gleich 3
voraussetzen. jetzt ist es mir egal ob größer drei 4 oder 5,
da ich ein recht gutes vorstellungsvermögen (und eine matheprogramm) hab kann ich mir vorstellen wie beide funktionen verlaufen und weiß dass ab einem gewissen wert 2^n größer sein wird als n^2. Aber mein Problem ist ja, dass ich noch nicht weiß wie uns die V I auf diesen Wert(n>3 oder n >4!) bringt. bei anderen Beispielen setzte ich auch für n die 1 ein, überprüfe ob es stimmt und mach danach den induktionsschritt...

Ich hoffe ich hab mein Problem deutlicher geschildert :-)
(Um es nochmal etwas abstrakter und in allgemeinerer form
zu formulieren: Bis jetzt denke ich halt dass man mit der VI
widersprüche beweisen kann wie 8>9. Dass der fehler bei
mir liegt ist ziemlich offensichtlich, wäre also dankbar wenn
mir das eine so aufzeigen kann, dass es so nicht ist, dass auch ich
das versteh.)
SirJective Auf diesen Beitrag antworten »

Wie würdest du denn konkret beweisen, dass 8>9 ist? Zeig mir das mal.

Für den Induktionsschritt von n auf n+1 ist es hier nötig, dass n>=3 ist und dass die Aussage für n gilt.
Leopold Auf diesen Beitrag antworten »

Dann treten wir den Beweis doch an. Damit auch alle mitkommen, gehe ich ganz langsam vor:















Irrlicht Auf diesen Beitrag antworten »

:P Verdammt hab ich lang gebraucht, um zu merken, wos hakt!!!!!!!!!!!!!!!!!!!
Hat jemand zufällig ein Loch gesehen, in das ich versinken kann?
Leopold Auf diesen Beitrag antworten »

Zur Strafe meinen neuesten Beitrag in "Buchstabenschüttler" in Schönschrift dreimal abschreiben! (Damit wir einmal wieder unsere alten Pauker-Methoden hervorkehren!)
Irrlicht Auf diesen Beitrag antworten »

Reichst wenn ich es dir in Schönkopie dreimal kopiere? *g* Und wieviele unterschiedliche Möglichkeiten sind das jetzt, mich zu permutieren?
Leopold Auf diesen Beitrag antworten »

siehe das Thema "Multinomialkoeffizienten"
Blind_Zyklop Auf diesen Beitrag antworten »

Leopold, N1 idea!

Aber ich hab zulange studiert um
auf sowas reinzufallen! Grundregel der
Aussagenlogik, aus etwas richtigem
darf nichts falsches folgen, so ehrlich sind wir!!

Und wenn man eine ungleichung mit einer negativen
Zahl multipliziert bzw dividiert (ln von zahlen kleiner eins
ist leider negativ) dreht sich die ungleichung!
Wodurch wir am Schlus 8<9 bekommen und meine
alte Frage zur VI bestehen bleibt und du mir leider
kein bisschen weitergeholfen hast, aber es war
interessant den fehler zu finden, bis ich alles ausgeschlossen hab,
bei dem ich mir auf anhieb sicher war.
(Potenz und Logarythmiergesetze waren nie meine Särke)

cya
Blind_Zyklop Auf diesen Beitrag antworten »

hups he did it again
Irrlicht Auf diesen Beitrag antworten »

@Zyklop:
Wie würdest du denn konkret beweisen, dass 8>9 ist? Zeig mir das mal.
Blind_Zyklop Auf diesen Beitrag antworten »

hey Irrliicht, sorry,
ich hoff dein Loch ist groß genug dasss
wir uns beide darin verstecken können.
Hab beim ersten mal schreiben nen fehler
gemacht der die Induktion für alle werte von
n funktionieren ließ. Das war das ganze Problem
und so gut versteckt dass ich es jetzt erst gesehen hab!
Meine Welt ist wieder in Ordnung und ich komm bald
aus dem Lock mim Irrlicht raus, cya 'n big THX
Mathespezialschüler Auf diesen Beitrag antworten »

Zitat:
Original von Leopold
Dann treten wir den Beweis doch an. Damit auch alle mitkommen, gehe ich ganz langsam vor:

















Hat man jetzt bewiesen, dass 8>9 ??? Rein theoretisch geht das doch gar nicht. Da es ja nicht stimmt, müsste man es ja auch nicht beweisen können verwirrt .
WebFritzi Auf diesen Beitrag antworten »

Nein, das ist kein Beweis, da in einer der Folgerungen etwas nicht stimmt. Anhaltspunkt für dich: ln(1/81) < 0.
Neue Frage »
Antworten »



Verwandte Themen

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