Beweis vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:24 Do 17.02.2011 | | Autor: | svcds |
| Aufgabe | Beweisen Sie:
[mm] \summe_{i=0}^{n} \bruch{i}{2} [/mm] < [mm] 2^{n-1} [/mm] |
Hi, also Induktionsanfang n=0 ist dann [mm] \bruch{0}{2} [/mm] < [mm] \bruch{1}{2} [/mm] ist wahr.
Dann Induktionsschritt:
also [mm] \summe_{i=0}^{n+1} \bruch{i}{2} [/mm] < [mm] 2^{n}
[/mm]
Dann hab ich
[mm] \summe_{i=0}^{n} \bruch{i}{2} +\bruch{n+1}{2} [/mm] < [mm] 2^{n} [/mm] und dann komm ich nicht weiter.
wer kann eben schnell helfen?
glg
|
|
| |
|
Hallo,
> Beweisen Sie:
>
> [mm]\summe_{i=0}^{n} \bruch{i}{2}[/mm] < [mm]2^{n-1}[/mm]
>
> Hi, also Induktionsanfang n=0 ist dann [mm]\bruch{0}{2}[/mm] <
> [mm]\bruch{1}{2}[/mm] ist wahr.
>
> Dann Induktionsschritt:
>
> also [mm]\summe_{i=0}^{n+1} \bruch{i}{2}[/mm] < [mm]2^{n}[/mm]
>
> Dann hab ich
>
> [mm]\summe_{i=0}^{n} \bruch{i}{2} +\bruch{n+1}{2}[/mm] < [mm]2^{n}[/mm] und
Das ist doch zu zeigen.
Nimm die linke Seite her und verwende die Induktionsvoraussetzung.
Die solltest du immer aufschreiben, das habe ich in der anderen Induktion von heute Nachmittag schon angekreidet 
Es ist [mm]\sum\limits_{i=0}^{n+1}\frac{i}{2}=\red{\sum\limits_{i=0}^{n}\frac{i}{2}} \ + \ \frac{n+1}{2}[/mm]
Auf den roten Term die IV anwenden:
[mm]< \ \red{2^{n-1}} \ + \ \frac{n+1}{2}[/mm]
Nun überlege dir, dass [mm]\frac{n+1}{2}<2^{n-1}[/mm] ist und du kannst weiter abschätzen zu [mm]< \ \red{2^{n-1}} \ + \ 2^{n-1}=2\cdot{}2^{n-1}=2^n[/mm]
> dann komm ich nicht weiter.
>
> wer kann eben schnell helfen?
>
> glg
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:35 Do 17.02.2011 | | Autor: | svcds |
ich hab das mit der IV gemacht, da steht dann bei mir
[mm] 2^{n-1} [/mm] + [mm] \bruch{n+1}{2} [/mm] < [mm] 2^{n}
[/mm]
aber wenn ich dann n=0 einsetze, steht da 1<1 und das geht ja nicht oder darf ich dann nicht n=0 einsetzen, weil ich ja n+1=0+1 dann habe oder wie? das ist die einzige Frage, die ich habe.
|
|
|
| |
|
Hallo nochmal,
> ich hab das mit der IV gemacht, da steht dann bei mir
>
> [mm]2^{n-1}[/mm] + [mm]\bruch{n+1}{2}[/mm] < [mm]2^{n}[/mm]
>
> aber wenn ich dann n=0 einsetze, steht da 1<1
Den Fall [mm]n=0[/mm] hast du doch im Induktionsanfang abgehandelt. [mm] $0<\frac{1}{2}$
[/mm]
Schreibe im Induktionsschritt [mm]n\to n+1[/mm]:
Sei [mm]n\in\IN, n>0[/mm] bel. und gelte bla (IV)
Dann ist zu zeigen, dass die Beh. auch für [mm]n+1[/mm] gilt.
Und das machst du wie beschrieben
> und das geht
> ja nicht oder darf ich dann nicht n=0 einsetzen, weil ich
> ja n+1=0+1 dann habe oder wie? das ist die einzige Frage,
> die ich habe.
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:50 Do 17.02.2011 | | Autor: | svcds |
wenn ich [mm] \summe_{i=0}^{n} \bruch{i}{2} [/mm] durch diese [mm] 2^{n-1} [/mm] ersetze, passt die gleichung nicht mehr....
dann steht da bei mir, wenn ich das umgeformt habe
[mm] 2^{n-1} [/mm] + [mm] \bruch{n+1}{2} [/mm] < [mm] 2^{n}
[/mm]
so setze ich dann testweise n=1 ein passt die Gleichung nicht.... oder hab ich etwas verkehrt gemacht?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:09 Do 17.02.2011 | | Autor: | Marcel |
Hallo,
> wenn ich [mm]\summe_{i=0}^{n} \bruch{i}{2}[/mm] durch diese [mm]2^{n-1}[/mm]
> ersetze, passt die
UN-
> gleichung nicht mehr....
>
> dann steht da bei mir, wenn ich das umgeformt habe
>
> [mm]2^{n-1}[/mm] + [mm]\bruch{n+1}{2}[/mm] < [mm]2^{n}[/mm]
>
> so setze ich dann testweise n=1 ein passt die Gleichung
> nicht.... oder hab ich etwas verkehrt gemacht?
wie soll jmd. das wissen, wenn Du die Rechnung nicht mal auszugsweise so hinschreibst, dass man sieht, was Du gemacht hast?
Es ist im Induktionsschritt so:
Vorausgesetzt wird, dass man (irgendein) $n [mm] \in \IN_0$ [/mm] hat, so dass für dieses [mm] $n\,$ [/mm] nun
[mm] $$(IV)\;\;\;\sum_{k=0}^n [/mm] k/2 < [mm] 2^{n-1}$$ [/mm]
gilt.
Dann will man zeigen:
Unter Benutzung von [mm] $(IV)\,$ [/mm] für [mm] $n\,$ [/mm] folgt, dass [mm] $(IV)\,$ [/mm] auch dann gilt, wenn man in [mm] $(IV)\,$ [/mm] das [mm] $\,n$ [/mm] durch [mm] $n+1\,$ [/mm] ersetzt.
(Wenn man das hat, dann weiß man: Wenn man irgendein [mm] $n_0 \in \IN$ [/mm] findet, so dass [mm] $(IV)\,$ [/mm] für dieses [mm] $n_0$ [/mm] gilt, so hat das "einen Dominoeffekt für alle natürlichen Zahlen [mm] $\ge n_0$: [/mm] wenn [mm] $(IV)\,$ [/mm] für [mm] $n_0$ [/mm] gilt, dann auch für [mm] $n_0+1$ [/mm] - aber wenn [mm] $(IV)\,$ [/mm] nun für [mm] $n_0+1$ [/mm] gilt, dann auch für [mm] $n_0+2$ [/mm] - etc. pp"
Bildlich: Stelle Dir aufgestellte Dominosteine vor. Der Induktionsbeweis sagt Dir dann quasi etwas relevantes darüber aus, ob oder ab wann welche Steine "nahe genug" beieinander stehen "bzgl. des Umfallens" (ein umgefallener Stein bedeute, dass die Behauptung für die dem Stein entsprechende Zahl wahr sei):
Die Induktionsvoraussetzung sagt Dir, dass es wenigstens "einen Startstein" gibt (meist ist das [mm] $n=0\,$ [/mm] oder [mm] $n=1\,$), [/mm] den man umwerfen darf, und der Induktionsschritt sagt Dir, wenn er denn gelingt, dass alle Steine hinter diesem Startstein dann sicher so nahe beeinander stehen, dass sie sich nacheinander umwerfen. Ein umgeworfener Stein bedeute dann, dass die Behauptung für diesen Stein zutrifft; ein stehender Stein sollte allerdings nur besagen, dass wir an dieser Stelle nochmal gucken müssen, ob wir ihn umwerfen dürfen oder nicht. Ein geprüfter Stein, für den die Behauptung nicht gilt, sollte allerdings markiert werden, dass er schonmal geprüft worden ist. Dabei ist übrigens jeder Stein, bspw. hier, mit einer natürlichen Zahl in eineindeutiger Weise verknüpft.
Du erkennst hier übrigens: Ein Induktionsbeweis ist nur dann vollständig, wenn man einen Induktionsstart hat und der Induktionsschritt gelingt. Denn was bringt es mir, wenn der Induktionsschritt gelingt, ich aber keinen Induktionsstart habe? Dann weiß ich zwar, dass alle Steine (meist eher alle Steine ab einem gewissen "Startstein") nahe genug beieinander stehen, so dass, wenn ich einen umwerfe, dann alle darauffolgenden umfallen würden, aber ich gar nicht weiß, dass ich einen umwerfen darf? Dann "kommen die Steine nie ins Rollen, weil man keinen Start-Umwerfstein hat..."
Andererseits: Was bringt es, einen Startstein zu haben, aber nicht zu wissen, dass (wenigstens alle Steine hinter diesem) so nahe beieinander stehen, dass jeder umfallende den dahinterstehenden mitnimmt?)
Nun zu Deiner Frage:
Im Induktionsschritt GILT (nach Verwendung von [mm] $(IV)\,$ [/mm] für [mm] $n\,$)
[/mm]
[mm] $$\sum_{k=1}^{n+1} [/mm] k/2 < [mm] 2^{n-1} +\frac{n+1}{2}\,.$$
[/mm]
ZEIGEN WILLST Du nun
[mm] $$\sum_{k=1}^{n+1} [/mm] k/2 < [mm] 2^n\,.$$
[/mm]
Wenn Du nun aber
[mm] $$(\star)\;\;2^{n-1} +\frac{n+1}{2} \;\red{\le}\; 2^n$$
[/mm]
wüßtest, so würdest Du das (was Du ZEIGEN WILLST) aus
[mm] $$\sum_{k=1}^{n+1} [/mm] k/2 < [mm] 2^{n-1} +\frac{n+1}{2} \le 2^n$$
[/mm]
folgern können.
(Beachte: $a < [mm] b\; \red{\le}\; [/mm] c [mm] \Rightarrow [/mm] a [mm] \;\blue{\text{<}}\; c\,.$)
[/mm]
Der Induktionsbeweis kann also als abgeschlossen betrachtet werden, wenn Du [mm] $(\star)$ [/mm] bewiesen hast.
Und da Du die Behauptung für alle $n [mm] \in \IN_0$ [/mm] zeigen sollst (vor allem aber, weil sie auch für alle $n [mm] \in \IN_0$ [/mm] gilt), sollte [mm] $(\star)$ [/mm] insbesondere auch für [mm] $n=0\,$ [/mm] gelten: Testen wir dies mal:
[mm] $$2^{-1}+\frac{1}{2} \le 2^0 \gdw [/mm] 1 [mm] \le 1\,.$$
[/mm]
Passt. Dein "Fehler" ist quasi, dass Du anstatt [mm] $(\star)$ [/mm] mit [mm] $\red{\le}$ [/mm] halt [mm] $(\star)$ [/mm] mit [mm] $\blue{<}$ [/mm] benutzen willst. Das geht auch. Aber dann musst Du den Induktionsbeweis so aufbauen, dass Du die Fälle $n=0, [mm] n=1\,$ [/mm] separat betrachtest, und im Induktionsbeweis dann die Behauptung für alle $n [mm] \ge [/mm] 2$ beweist.
Im Induktionsbeweis findet also beim (Induktionsstart) nochmal eine Prüfung mit [mm] $n=2\,$ [/mm] statt, und die Ungleichung, wenn man in [mm] $(\star)$ [/mm] dann [mm] $\le$ [/mm] durch $<,$ ersetzt, wird dann für alle $n [mm] \ge [/mm] 2$ bewiesen und benutzt. (Für $n=0$ steht in $(star)$ ja $1 [mm] \le [/mm] 1$ und für [mm] $n=1\,$ [/mm] steht in [mm] $(\star)$ [/mm] $2 [mm] \le 2\,,$ [/mm] also kann man [mm] $;\;2^{n-1} +\frac{n+1}{2} [/mm] < [mm] 2^n$ [/mm] (also die ECHT-KLEINER-VERSION von [mm] $(\star)$) [/mm] sicher, wenn überhaupt, erst für alle $n [mm] \ge [/mm] 2$ beweisen.)
P.S.:
Weil DU bei Deinem Induktionsbeweis die Ungleichung [mm] $(\star)$ [/mm] in der ECHT-KLEINER-VERSION benutzen willst, kommst Du bei Dir auch für [mm] $n=0\,$ [/mm] und [mm] $n=1\,$ [/mm] in Schwierigkeiten. Benutzt Du einfach meine Ungleichung [mm] $(\star)$, [/mm] also die KLEINERGLEICH-Version, so ist das, wie oben geschrieben, auch hinreichend für die Lösung der Aufgabe und die "Testfälle [mm] $n=0\,$ [/mm] und [mm] $n=1\,$ [/mm] liefern in [mm] $(\star)$ [/mm] auch keine Probleme, da dort dann KLEINERGLEICH steht:
[mm] $$n=0:\;\; [/mm] 1 [mm] \le [/mm] 1$$
und
[mm] $$n=1:\;\; [/mm] 2 [mm] \le 2\,.$$"
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:17 Do 17.02.2011 | | Autor: | svcds |
ich weiß, wie man vollständige Induktion macht, da steht in der Aufgabenstellung kein "kleiner gleich" sondern nur ein "kleiner als". das verwirrt mich, daher glaub ich der prof hat sich vertan. weil ich ja auch für n=0 und n=1 falsche Ergebnisse bekomme also 1<1 und so weiter. also ich leg die aufgabe mal weg. dank euch trotzdem!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:38 Do 17.02.2011 | | Autor: | Marcel |
Hallo,
> ich weiß, wie man vollständige Induktion macht, da steht
> in der Aufgabenstellung kein "kleiner gleich" sondern nur
> ein "kleiner als". das verwirrt mich, daher glaub ich der
> prof hat sich vertan. weil ich ja auch für n=0 und n=1
> falsche Ergebnisse bekomme also 1<1 und so weiter. also ich
> leg die aufgabe mal weg. dank euch trotzdem!
nein, dann missverstehst Du das, was ich geschrieben habe. Die Ungleichung
[mm] $$\sum_{k=0}^n [/mm] k/2 < [mm] 2^{n-1}$$
[/mm]
zeigst Du per Induktion. Diese enthält das ECHT-KLEINER Zeichen.
Im INDUKTIONSSCHRITT brauchst Du eine weitere Ungleichung, nämlich
[mm] $$(\star)\;\;2^{n-1} +\frac{n+1}{2} \;\red{\le}\; 2^n\,.$$
[/mm]
(Es reicht, diese zu beweisen, weil aus $a < b [mm] \le [/mm] c$ schon $a < [mm] c\,$ [/mm] folgt.!!)
In der Version Deines Induktionsbeweise willst Du im Induktionsschritt aber nicht [mm] $(\star)$ [/mm] benutzen, sondern stattdessen
$$ [mm] (\star_2)\;\;2^{n-1} +\frac{n+1}{2} \;\red{<}\; 2^n\,.$$
[/mm]
Die Ungleichung [mm] $(\star_2)$ [/mm] gilt aber nur für alle natürlichen $n [mm] \ge 2\,.$ [/mm] Also musst DU, wenn Du Deinen Induktionsbeweis in dieser Form führst, erstmal die Ungleichung
[mm] $$\sum_{k=0}^n [/mm] k/2 < [mm] 2^{n-1}$$
[/mm]
für [mm] $n=0\,$ [/mm] und [mm] $n=1\,$ [/mm] separat nachweisen. Danach sagst Du:
Die Ungleichung gilt auch für alle $n [mm] \ge 2\,.$ [/mm] Beweis:
Induktionsstart mit [mm] $n=2\,$ [/mm] (ist das gleiche, wie, wenn man den Fall [mm] $n=2\,$ [/mm] separat aufführt.)
Induktionsschritt:
Sei nun $n [mm] \ge [/mm] 2$ mit
[mm] $$\sum_{k=0}^n [/mm] k/2 < [mm] 2^{n-1}$$
[/mm]
gefunden. Dann gilt:
.
.
.
Weil, wegen $n [mm] \ge 2\,,$ [/mm] nun auch
$$ [mm] (\star_2)\;\;2^{n-1} +\frac{n+1}{2} \;\red{<}\; 2^n\,$$
[/mm]
gilt, folgt
.
.
.
Das ist eine vollkommen saubere Variante der Induktion. Nur geht es halt, wenn man anstatt der Ungleichung [mm] $(\star_2)\,,$ [/mm] die für alle natürlichen $n [mm] \ge [/mm] 2$ gilt, die Ungleichung [mm] $(\star)\,,$ [/mm] die für alle $n [mm] \in \IN_0$ [/mm] gilt, verwendet, halt schneller.
Bei Dir steht dann im Induktionsschritt mittels [mm] $(\star_2)$ [/mm] sowas wie
[mm] $$\summe [/mm] ... < irgendwas < nochwas$$
[mm] $$\Rightarrow \summe [/mm] ... < [mm] nochwas\,,$$
[/mm]
bei der Variante mit [mm] $(\star)$ [/mm] steht dann da
[mm] $$\summe [/mm] ... < irgendwas [mm] \le [/mm] nochwas$$
[mm] $$\Rightarrow \summe [/mm] ... < [mm] nochwas\,.$$
[/mm]
Im Ergebnis also die behauptete Ungleichung mit [mm] $<\,.$ [/mm] Nur das "Hilfsmittel" im Induktionsschritt, welches in [mm] $(\star)$ [/mm] in einer KLEINERGLEICH-VARIANTE formuliert ist, wird durch ein (minimal) anderes Hilfsmittel [mm] $(\star_2)$ [/mm] ersetzt - wobei [mm] $(\star_2)$ [/mm] die KLEINER-VARIANTE von [mm] $(\star)$ [/mm] ist. (Beachte: [mm] $<\,$ [/mm] ist eine "stärkere" Ungleichung als [mm] $\le$: [/mm] Denn aus $r < [mm] s\,$ [/mm] folgt unmittelbar $r [mm] \le s\,.$)
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:55 Do 17.02.2011 | | Autor: | svcds |
okay versteh ich du tippst ja ganz schön viel :) hatte mich eben verwirrt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:06 Do 17.02.2011 | | Autor: | abakus |
> ich weiß, wie man vollständige Induktion macht, da steht
> in der Aufgabenstellung kein "kleiner gleich" sondern nur
> ein "kleiner als". das verwirrt mich, daher glaub ich der
> prof hat sich vertan. weil ich ja auch für n=0 und n=1
> falsche Ergebnisse bekomme also 1<1 und so weiter. also ich
> leg die aufgabe mal weg. dank euch trotzdem!
Hallo,
das ist nicht wahr. Du kannst mit n=0 oder n=1 DIREKT in die behauptete Aussage gehen und sehen, dass die Behauptung für diese Werte stimmt.
DANACH verwenden wir ABSCHÄTZUNGEN, um zu zeigen, dass aus der Gültigkeit der Ungleichung für gewisse n auch die Gültigkeit für nachfolgende n folgt. Diese Abschätzungen sind nur unter Umständen zu großzügig, sodass sie auf n=0 oder n=1 noch nicht angewendet werden können.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:43 Fr 18.02.2011 | | Autor: | svcds |
okay verstanden, also eine Aufgabe mit Trick :) danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:21 Do 17.02.2011 | | Autor: | Marcel |
Hallo,
> Beweisen Sie:
>
> [mm]\summe_{i=0}^{n} \bruch{i}{2}[/mm] < [mm]2^{n-1}[/mm]
es ist zwar nicht unbedingt erwünscht, weil Du bei der Aufgabenstellung vermutlich einfach nur Induktion üben sollst, aber der kleine Gauß lehrt uns wegen
[mm] $$\sum_{i=0}^n \frac{i}{2}=\frac{1}{2}\sum_{i=1}^n i\,,$$
[/mm]
dass
[mm] $$\sum_{i=0}^n \frac{i}{2}=\frac{1}{2}*\frac{n}{2}(n+1)=\frac{n(n+1)}{4}\,,$$
[/mm]
ist. Somit kann man sagen, dass
[mm] $$\summe_{i=0}^{n} \bruch{i}{2} [/mm] < [mm] 2^{n-1}$$
[/mm]
[mm] $$\gdw \frac{n(n+1)}{4} [/mm] < [mm] 2^{n-1}$$
[/mm]
[mm] $$\gdw [/mm] n(n+1) < [mm] 2^{n+1}$$
[/mm]
gilt.
Somit kann man auch letztere Ungleichung per Induktion beweisen, um der Aufgabenstellung gerecht zu werden.
Gruß,
Marcel
|
|
|
|
