nehmen das grade in mathe durch, ich komm da auf keinen grünen zweig.
erstma bsp:
[code]2^(n-1) > n^2
Induktionsanfang: A(7): 64=49; 7 ist erstes n, für das die UG stimmt
Iduktionsannahme: A(n) sei richtig
Induktionsschluss: A(n)=>A(n+1)
A(n+1): 2^n > (n+1)^2[/code]
soweit.. aber wie gehe ich genau vor?
und ich versteh dann immer noch nicht, WIE die vollst. Induktion die Ungleichung 'beweist'..!
helft mir
heheZitat von LuckyLuke
nehmen das grade in mathe durch, ich komm da auf keinen grünen zweig.
erstma bsp:
[code]2^(n-1) > n^2
Induktionsanfang: A(7): 64=49; 7 ist erstes n, für das die UG stimmt
Iduktionsannahme: A(n) sei richtig
Induktionsschluss: A(n)=>A(n+1)
A(n+1): 2^n > (n+1)^2[/code]
soweit.. aber wie gehe ich genau vor?
und ich versteh dann immer noch nicht, WIE die vollst. Induktion die Ungleichung 'beweist'..!
helft mir
ich bin zwar Elektriker und hab das in der berufsschule mehr als nur durchgekaut dieses Thema mit reiner Induktion usw und umwandlungsverhältniss der spann, Strom u. der wicklungen.....aber das ist Müll den ich ned verstehe
steffen m. HILF MIR!
jetzt mal ohne scheiß...des thema war mein horror, ich wusst wenn des im abi drankommt geh ich unter...weiß zwar um was es da geht, aber keine ahnung we die da immer draufgekommen sind, ob ne formel auch für jedes beliebige n+1 gilt...
ja das "draufkommen" ist sone sache.. mathe halt! alles krank
ich hatte Mathe-LK un das thema war echt horrorja das "draufkommen" ist sone sache.. mathe halt! alles krank
wir ham den scheiß bisher nur mit so Gleichungen. Die muss man dann halt iwie gleichsetzen und gucken, ob die gleich sind.
musst du da nich nur noch rechnen und versuchen das auf beiden seiten das gleiche rauszubekommem? haben das auch grade... klausur am mittwoch wird sicher lustig^^nehmen das grade in mathe durch, ich komm da auf keinen grünen zweig.
erstma bsp:
[code]2^(n-1) > n^2
Induktionsanfang: A(7): 64=49; 7 ist erstes n, für das die UG stimmt
Iduktionsannahme: A(n) sei richtig
Induktionsschluss: A(n)=>A(n+1)
A(n+1): 2^n > (n+1)^2[/code]
soweit.. aber wie gehe ich genau vor?
und ich versteh dann immer noch nicht, WIE die vollst. Induktion die Ungleichung 'beweist'..!
helft mir
ich rechne dass ma auf papier. vielleicht komm ich weiter
edit: nein,nich weitergekommn
weil 2^n > n²+1 genau das gegenteil beweisn würde
Hallo,
Ich versuch's...
Induktionsanfang (IA) oder auch Induktionsverankerung: Wir wählen hier n=7, da das das kleinste positive ganze "n" ist, für das die Ungleichung erfüllt ist. Das ergibt dann einfach durch Einsetzen:[code]
2^6 > 7^2
<---> 64 > 49[/code]
Induktionshypothese (IH): Wir nehmen an, dass die Ungleichung für "n" gilt, dass also:[code]
2^(n-1) > n^2[/code]
wahr ist.
Unter der (unbewiesenen!) Annahme, dass die IH, also die Ungleichung, wahr ist, versuchen wir nun zu zeigen, dass eben wenn die IH wahr ist, auch die Ungleichung für das nächste "n" gilt (also für "n+1"). Die Idee dahinter ist wie folgt: Ob die IH wahr ist, wissen wir nicht. Das wollen wir ja beweisen. Das geht aber nicht unmittelbar, wir müssten es, wenn wir es direkt versuchen würden, ja für alle "n" (also für unendlich viele Zahlen) austesten - das geht in endlicher Zeit nicht.
Der Trick dabei ist: Wir zeigten bereits im IA, dass die Ungleichung für ein ganz bestimmtes "n" gilt, hier "n=7".
Im folgenden Induktionsschritt (IS) zeigen wir, dass wenn wir ein "n" haben, für das die Ungleichung gilt, sie auch für das darauffolgende "n", also für "n+1", gültig ist.
Induktionsschritt (IS): Wir setzen jetzt einfach mal "n+1" statt "n" in die Ungleichung ein. Das können wir ja einfach machen. Wir erhalten:[code]
2^n > (n+1)^2[/code]
Das wiederum können wir jetzt umschreiben, ich ziehe auf der linken Seite eine "2" raus und löse rechts die Klammer auf:[code]
2 * 2^(n-1) > n^2 + 2n + 1[/code]
Das können wir auch so schreiben:[code]
2^(n-1) + 2^(n-1) > n^2 + 2n + 1
---\ /--- ---\ /---
| |
A B[/code]
Ich weiß aber auch (laut IH), dass[code]
2^(n-1) > n^2[/code]
gilt. Das (also die IH) verwenden wir jetzt. Damit haben wir ja schon erledigt, dass der Summand "B" größer als "n^2" ist (Du kannst statt "B" natürlich auch den Summanden "A" nehmen). Damit reicht es doch, noch zu zeigen, dass der Summand "A" größer oder gleich "2n + 1" ist. Haben wir das gezeigt, dann haben wir die Ungleichung für "n+1" bewiesen (unter der Annahme, dass die für "n" gilt).
Zu zeigen bleibt also:[code]
2^(n-1) > 2n + 1[/code]
Nun können wir hier wieder die IH anwenden. Die besagt, dass "2^(n-1)" ja größer als "n^2" ist. Also genügt es, zu zeigen, dass:[code]
n^2 > 2n + 1[/code]
Denn "2^(n-1)" ist laut IH größer als "n^2". Und wir zeigen jetzt, dass "n^2" größer als "2n+1" ist. Damit hätten wir gezeigt, dass "2^(n-1)" größer als "2n + 1" ist.
Also bleibt zu zeigen:[code]
n^2 > 2n + 1[/code]
Das ist aber leicht durch Umformung zu erledigen, denn das ist ja nichts Anderes als:[code]
n^2 > 2n + 1
<---> n^2 - 2n - 1 > 0[/code]
Und das ist wahr für alle "n", die größer als "1 + Wurzel(2)" sind. Das sollte es damit gewesen sein.
Nochmals zur Vorgehensweise:
- Wir zeigen im IA, dass die Ungleichung für ein bestimmtes "n" erfüllt ist.
- Wir schreiben im IS die Aussage für "n+1" hin und verwenden dabei aber die (zunächst unbewiesene und zu beweisende) IH, um die Aussage für "n+1" auf etwas "Einfaches", etwas "Einsichtiges" zurückzuführen.
Wir haben damit gezeigt, dass wenn die IH gilt, dass dann auch die Aussage für den Nachfolger gilt. Zusammen mit der IA haben wirs aber für alle Zahlen, die größer als die bei der IA verwendeten (hier: n=7) bewiesen. Wir haben quasi einen Beweiser programmiert (in Gedanken), der bei "n=7" verankert losläuft und es (in Gedanken) jeweils für den Nachfolger beweist. Aus der Gültigkeit für "n=7" folgt die Gültigkeit für "n=8". Aus der Gültigkeit für "n=8" folgt die Gültigkeit für "n=9", usw...
Mit anderen Worten: Die Vollst. Induktion zerlegt das Problem, eine Aussage für alle Zahlen zu beweisen in unendlich viele Teile: Wir zeigen (im IS), dass wir immer von der Gültigkeit für eine Zahl auf die Gültigkeit für die Nachfolgerzahl schließen können. Und dann verankern wir an einer "Startzahl" (in der IA). Damit haben wir's für alle "n", die größer als die "Startzahl" sind, gezeigt. Die IH ist damit bewiesen.
Etwas irritiert hat mich bei der Vollst. Induktion, als wir das in der Jahrgang 12 seinerzeit durchgesprochen hatten, dass wir die IH im IS selber verwenden dürfen, wo wir doch gerade das, was in der IH steht, beweisen müssen und somit noch gar nicht bewiesen wurde. Man darf sich aber hier nicht irritieren lassen: Wir zeigen ja im IS nicht die Gültigkeit der IH für "n+1" als Ganzes, sondern wir zeigen im IS lediglich, dass, wenn die IH stimmt, die Ungleichung auch für den Nachfolger "n+1" gilt. Für alle "n" (hier "n>=7") gilt's ja erst durch die Verankerung mittels der IA.
Ich hab's nur auf die Schnelle und im Stress runtergetippt, kann gut sein, dass Fehler drin sind oder es elegantere Lösungen gibt. Korrigiert oder ergänzt mich gegebebenfalls. Bei Groups-Google wurde ich z.B. auch gerade fündig (oder auch hier).
HTH,
Steffen
Tschüsch Amona !
Und genau was willst Du damit sagen? ;-)
Steffen
danke erstmal, steffen!
ich werd mir das mal anschauen..
Keine Ursache. Ansonsten habe ich selber die Induktion bei so Ungleichungsgeschichten auch eher ungern gemacht. Beweise zu Aussagen über Folgen (z.B. Fibonacci) waren mir persönlich da irgendwie lieber.
Wichtig ist halt, dass die Grundidee der Induktion klar ist. Dass man also weiß, warum man die zunächst unbewiesene IH im IS verwenden darf. Und dann muss man im IS eben schauen, ob man das, was da steht, unter Anwendung der IH auf etwas Einsichtiges oder Klares formal zurückführen kann.
Wenn Du noch Fragen hast, kannst Du ja mal in der Newsgroup "de.sci.mathmeatik" noch nach Induktionsbeweisen suchen oder einfach hier wieder posten.
Gruß,
Steffen
d.h., ich benutze den IS um ihn auf eine einfache ungleichung zu reduzieren, die offensichtlich zeigt, dass die linke seit z.B. kleiner/größer ist als 0 o.ä.
angenommen mein (umgeformter) IS sieht so aus:
n²>2
heißt, n>wurzel_2. aber was fange ich genau damit an?
ich mein, gilt dann für die ursp. zu beweisende ungleichung, dass sie nur wahr ist für n>wurzel_2.. ?
Würde ich spontan so sagen, ja.
Steffen
Benutzer, die dieses Thema gelesen haben: 0
Zitieren
Tequilla
Lesezeichen