Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:14 Di 17.05.2011 | | Autor: | BenMath |
| Aufgabe | Gegeben sei die Gleichung [mm] S_{i} [/mm] = [mm] \bruch{i(i+1)}{2}
[/mm]
Zeigen Sie: für alle (x, y) ∈ [mm] \IN [/mm] × [mm] \IN [/mm] gilt [mm] S_{x+y}+x |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo.
Ich denke die Annahme lässt sich durch vollständige Induktion beweisen. Leider habe ich bei dieser Beweismethode große Verständnisprobleme. Folgende Gedanken habe ich mir gemacht:
Ich weiß nicht genau ob man den Induktionsbeweiß über x oder y führen muss. Ich habe es über x versucht:
Induktionsannahme: [mm] S_{x+y}+x
Induktionsanfang: [mm] S_{0+y}+0=S_{y}
Induktionsbehauptung: [mm] S_{x+1+y}+x+1=S_{x+y+1}+x+1
Induktionsschritt: [mm] S_{x+1+y}+x+1 [/mm] < ...
Ab hier weiß ich nicht wie man den Beweis weiterführt.
Überlegung: Ich müsste ja eigentlich zeigen, dass [mm] x+1
Kann mir jemand weiterhelfen? Ich hab anscheinend noch irgendwo einen Denkfehler bzw. eine Denkblockade beim Thema vollständige Induktion.
Grüße und Danke im Vorraus.
|
|
| |
|
Hallo BenMath, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich habe den Eindruck, Du wirfst da Variablen durcheinander.
Das passiert bei solchen Aufgaben allerdings auch schnell.
> Gegeben sei die Gleichung [mm]S_{i}[/mm] = [mm]\bruch{i(i+1)}{2}[/mm]
> Zeigen Sie: für alle (x, y) ∈ [mm]\IN[/mm] × [mm]\IN[/mm] gilt
> [mm]S_{x+y}+x
>
> Hallo.
> Ich denke die Annahme lässt sich durch vollständige
> Induktion beweisen.
Das denke ich auch. Wenn die Annahme überhaupt richtig ist...
Schneller lässt sie sich allerdings so beweisen:
Zeige erst [mm] S_{i+1}=i+1+S_{i}
[/mm]
Dann zeige [mm] x
Fertig.
Ok, aber zurück zur vollständigen Induktion. Die sollte genauso gut klappen.
> Leider habe ich bei dieser
> Beweismethode große Verständnisprobleme. Folgende
> Gedanken habe ich mir gemacht:
>
> Ich weiß nicht genau ob man den Induktionsbeweißs über x
> oder y führen muss. Ich habe es über x versucht:
Auch das sollte beides gehen, aber ich würde auch den Weg über x wählen.
Das heißt zugleich, dass y als fest angenommen wird, also ein Parameter ist.
> Induktionsannahme: [mm]S_{x+y}+x
> Induktionsanfang: [mm]S_{0+y}+0=S_{y}
Das stimmt für alle [mm] y\in\IN. [/mm] Der Anfang ist also ok.
> Induktionsbehauptung:
> [mm]S_{x+1+y}+x+1=S_{x+y+1}+x+1
> Induktionsschritt: [mm]S_{x+1+y}+x+1[/mm] < ...
> Ab hier weiß ich nicht wie man den Beweis weiterführt.
Induktion klappt nur, wenn man den Induktionsschritt auf zwei unterschiedlichen Wegen gehen kann, also hier einmal über die explizite Formel für [mm] S_i [/mm] etc. Der andere Weg ist allerdings nicht deutlich; wahrscheinlich musst Du also tatsächlich so vorgehen, wie Du jetzt vorschlägst. (Da ist der zweite Weg eben die rekursive Darstellung von [mm] S_i, [/mm] nämlich [mm] S_{i+1}=i+1+S_i
[/mm]
> Überlegung: Ich müsste ja eigentlich zeigen, dass
> [mm]x+1
> langsamer wächst als die rechte Seite für alle x ∈ [mm]\IN.[/mm]
Ja, schon richtig. Allerdings ist genau hier die Variablenverwirrung eingetreten, denn das i aus der Definition hat hier nichts mehr zu suchen.
Du musst zeigen, dass [mm] x+1
Das ist nicht schwierig.
> Das folgt daraus dass i=x+y und somit x<=i, denn selbst
> wenn x=i würde gelten: i+1<i+2.>
Ja, richtig, wenn auch kraus formuliert. Aber wozu nützt es denn, dann erst das i einzuführen?
> Kann mir jemand weiterhelfen? Ich hab anscheinend noch
> irgendwo einen Denkfehler bzw. eine Denkblockade beim Thema
> vollständige Induktion.
Nein, das sieht doch ganz gekonnt aus, wenn Du es mal sauber formulierst.
Einfacher ist aber der direkte Beweis, siehe oben.
> Grüße und Danke im Vorraus.
Grüße
reverend
</i+2.>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:53 Di 17.05.2011 | | Autor: | BenMath |
Hi reverend,
danke für die ausführliche Antwort. Ich habe mal versucht den Beweis formal zusammenzuschustern. Den Weg der vollständigen Induktion hab ich gewählt weil das momentan eins unserer Kernthemen ist und ich deswegen die Beweismethode üben möchte.
Gegeben sei die Gleichung $ [mm] S_{i} [/mm] $ = $ [mm] \bruch{i(i+1)}{2} [/mm] $
Zeigen Sie: für alle (x, y) ∈ $ [mm] \IN [/mm] $ × $ [mm] \IN [/mm] $ gilt $ [mm] S_{x+y}+x
Induktionsannahme: $ [mm] S_{x+y}+x
Induktionsanfang: $ [mm] S_{0+y}+0=S_{y}
Induktionsbehauptung: $ [mm] x+1
Induktionsschritt: $ x+1 $ < [mm] S_{x+y+2}-S_{x+y+1}=\bruch{(x+y+2)(x+y+3)}{2}-\bruch{(x+y+1)(x+y+2)}{2}=\bruch{x^2+2xy+5x+y^2+5y+6}{2}-\bruch{x^2+2xy+3x+y^2+3y+2}{2}=\bruch{2x+2y+4}{2}=x+y+2
[/mm]
Ich hoffe der Beweis ist so einigermaßen korrekt. Morgen ist Übungsstunde, da werd ich dann sehen was gegebenenfalls zu verbessern ist.
Grüße und danke nochmal.
|
|
|
| |
|
> Hi reverend,
> danke für die ausführliche Antwort. Ich habe mal
> versucht den Beweis formal zusammenzuschustern. Den Weg
> der vollständigen Induktion hab ich gewählt weil das
> momentan eins unserer Kernthemen ist und ich deswegen die
> Beweismethode üben möchte.
Ein Beispiel, in dem man besser darauf verzichten würde,
finde ich dazu zwar nicht besonders geeignet ...
> Gegeben sei die Gleichung [mm]S_{i}[/mm] = [mm]\bruch{i(i+1)}{2}[/mm]
> Zeigen Sie: für alle (x, y) ∈ [mm]\IN[/mm] × [mm]\IN[/mm] gilt
> [mm]S_{x+y}+x
> Induktionsannahme: [mm]S_{x+y}+x
> Induktionsanfang: [mm]S_{0+y}+0=S_{y}
Und wo zeigst du, dass dieser Induktionsanfang
tatsächlich stimmt ?
> Induktionsbehauptung: [mm]x+1
Warum formulierst du hier nicht einfach die zu zeigende
Ungleichung für den Fall x+1 anstelle von x ?
Die würde lauten:
[mm]S_{(x+1)+y}+(x+1)
> Induktionsschritt: [mm]x+1[/mm] <
> [mm]S_{x+y+2}-S_{x+y+1}=\bruch{(x+y+2)(x+y+3)}{2}-\bruch{(x+y+1)(x+y+2)}{2}=\bruch{x^2+2xy+5x+y^2+5y+6}{2}-\bruch{x^2+2xy+3x+y^2+3y+2}{2}=\bruch{2x+2y+4}{2}=x+y+2[/mm]
Jetzt hast du keineswegs einen Induktionsschritt durchgeführt
(du verwendest ja die "Induktionsannahme" gar nicht !), sondern
einfach das schlichte Ausmultiplizieren und Nachrechnen, das
ich von Anfang an empfohlen habe, für den Fall x+1 (anstatt
für x) ...
> Ich hoffe der Beweis ist so einigermaßen korrekt.
Ein Beweis durch vollständige Induktion ist es aber
jedenfalls nicht !
> Morgen ist Übungsstunde, da werd ich dann sehen was
> gegebenenfalls zu verbessern ist.
>
> Grüße und danke nochmal.
LG Al-Chw.
|
|
|
| |
|
> Gegeben sei die Gleichung [mm]S_{i}[/mm] = [mm]\bruch{i(i+1)}{2}[/mm]
> Zeigen Sie: für alle (x, y) ∈ [mm]\IN[/mm] × [mm]\IN[/mm] gilt
> [mm]S_{x+y}+x
> Hallo.
> Ich denke die Annahme lässt sich durch vollständige
> Induktion beweisen.
Warum denn überhaupt vollständige Induktion ?
Man kann doch einfach einsetzen und nachrechnen !
LG Al-Chw.
|
|
|
| |
|
weil zu beweisen ist, dass es für alle x,y aus N gilt ;) - hätte es nicht anders gelöst
|
|
|
| |
|
> weil zu beweisen ist, dass es für alle x,y aus N gilt ;) -
> hätte es nicht anders gelöst
Dabei benützt du aber bestimmt ohne Wimpernzucken
innerhalb eines solchen Beweises die Tatsache, dass
die üblichen Rechengesetze wie z.B. das Distributiv-
gesetz für beliebige natürliche Zahlen gelten !
LG Al-Chw.
|
|
|
| |
|
ja .. soetwas gibt man auch an dass man es tut ;) oder WAS willst du mir sagen/fragen/vorwerfen ?!
|
|
|
| |
|
> ja .. soetwas gibt man auch an dass man es tut ;) oder WAS
> willst du mir sagen/fragen/vorwerfen ?!
Ich wollte doch einfach sagen, dass ein Induktionsbeweis
für die vorliegende Aufgabe einfach überflüssig ist.
Die Aufgabe lautete:
Gegeben sei die Gleichung $ [mm] S_{i} [/mm] $ = $ [mm] \bruch{i(i+1)}{2} [/mm] $
Zeigen Sie: für alle (x, y) ∈ $ [mm] \IN [/mm] $ × $ [mm] \IN [/mm] $ gilt $ [mm] S_{x+y}+x
Die gegebene Gleichung (mit dem Index i) ist eine für
alle [mm] i\in\IN [/mm] gültige Definition, und nicht eine noch zu
beweisende Gleichung.
In der zu zeigenden Ungleichung kommen die Terme [mm] S_{x+y} [/mm] und
[mm] S_{x+y+1} [/mm] vor, wobei x und y für natürliche Zahlen stehen.
Dass x+y und x+y+1 dann auch natürliche Zahlen sind, muss
wohl so wenig neu bewiesen werden als etwa das Distributiv-
gesetz. Nach der Definition von [mm] S_i [/mm] ergibt sich dann:
$\ [mm] S_{x+y}\ [/mm] =\ [mm] \bruch{(x+y)*(x+y+1)}{2}$
[/mm]
$\ [mm] S_{x+y+1}\ [/mm] =\ [mm] \bruch{(x+y+1)*(x+y+2)}{2}$
[/mm]
und $\ [mm] S_{x+y+1}\ [/mm] -\ [mm] S_{x+y}\ [/mm] =\ [mm] \bruch{(x+y+1)}{2}\ *(\underbrace{(x+y+2)-(x+y)}_2)\ [/mm] =\ x+y+1$
Weil [mm] y\in\IN [/mm] , ist natürlich y>0 und x+y+1>x .
Also folgt $\ [mm] S_{x+y+1}\ [/mm] -\ [mm] S_{x+y}\ [/mm] >\ x$ oder
$ [mm] S_{x+y}+x
Vollständige Induktion ist für diesen Beweis überhaupt
nicht erforderlich, sondern nur die Anwendung der
"normalen" in [mm] \IN [/mm] gültigen Rechenregeln (für deren
ursprünglichen Beweis man eventuell schon auch
einmal vollständige Induktion eingesetzt hat).
LG Al-Chw.
|
|
|
| |
|
nur weil sie nicht erforderlich ist heißt es noch lange nicht dass es nicht stimmt ;)
> Die Aufgabe lautete:
>
> Gegeben sei die Gleichung [mm]S_{i}[/mm] = [mm]\bruch{i(i+1)}{2}[/mm]
> Zeigen Sie: für alle (x, y) ∈ [mm]\IN[/mm] × [mm]\IN[/mm] gilt
> [mm]S_{x+y}+x
>
> Die gegebene Gleichung (mit dem Index i) ist eine für
> alle [mm]i\in\IN[/mm] gültige Definition, und nicht eine noch
> zu
> beweisende Gleichung.
und das weißt du woher ? - Angabe ist viel zu kurz - also musst du grundsätzlich alles beweisen was geht (wäre zumindest in wien so). sorry aber wir hatten auch solche gleichungen auf der Uni und MUSSTEN vollständige induktion verwenden
> In der zu zeigenden Ungleichung kommen die Terme [mm]S_{x+y}[/mm]
> und
> [mm]S_{x+y+1}[/mm] vor, wobei x und y für natürliche Zahlen
> stehen.
> Dass x+y und x+y+1 dann auch natürliche Zahlen sind,
> muss
> wohl so wenig neu bewiesen werden als etwa das
> Distributiv-
> gesetz.
würde ich doch nicht ;) hab ja geschrieben "ja .. soetwas gibt man auch an dass man es tut ;)" bevor man mit einem beweis beginnt definiert bzw skizziert man sich ja einige sachen ;) (wie zb dass alle allgemein gültigen rechengesetze gelten / oder auch nicht)
> Nach der Definition von [mm]S_i[/mm] ergibt sich dann:
>
> [mm]\ S_{x+y}\ =\ \bruch{(x+y)*(x+y+1)}{2}[/mm]
>
> [mm]\ S_{x+y+1}\ =\ \bruch{(x+y+1)*(x+y+2)}{2}[/mm]
>
> und [mm]\ S_{x+y+1}\ -\ S_{x+y}\ =\ \bruch{(x+y+1)}{2}\ *(\underbrace{(x+y+2)-(x+y)}_2)\ =\ x+y+1[/mm]
>
> Weil [mm]y\in\IN[/mm] , ist natürlich y>0 und x+y+1>x .
> Also folgt [mm]\ S_{x+y+1}\ -\ S_{x+y}\ >\ x[/mm] oder
> [mm]S_{x+y}+x
auf das selbe würde ich auch kommen ;)
> Vollständige Induktion ist für diesen Beweis überhaupt
> nicht erforderlich, sondern nur die Anwendung der
> "normalen" in [mm]\IN[/mm] gültigen Rechenregeln (für deren
> ursprünglichen Beweis man eventuell schon auch
> einmal vollständige Induktion eingesetzt hat).
ich gebe dir schon recht dass die vollständige induktion nicht erforderlich sein muss bei diesem beispiel - jedoch würde ich auch ein bisschen drauf achten, das der herr kollege meinte ihr hauptthemengebiet sei zur zeit die vollständige induktion.
solange der beweis richtig durchgeführt wird und solange das ergebnis passt sollte man meiner meinung nicht am "i-tüpfelchen" rumreiten
LG Scherzkrapferl
|
|
|
| |
|
> nur weil sie nicht erforderlich ist heißt es noch lange
> nicht dass es nicht stimmt ;)
>
>
> > Die Aufgabe lautete:
> >
> > Gegeben sei die Gleichung [mm]S_{i}[/mm] = [mm]\bruch{i(i+1)}{2}[/mm]
> > Zeigen Sie: für alle (x, y) ∈ [mm]\IN[/mm] × [mm]\IN[/mm] gilt
> > [mm]S_{x+y}+x
> >
> > Die gegebene Gleichung (mit dem Index i) ist eine für
> > alle [mm]i\in\IN[/mm] gültige Definition, und nicht eine noch
> > zu
> > beweisende Gleichung.
>
> und das weißt du woher ? - Angabe ist viel zu kurz - also
> musst du grundsätzlich alles beweisen was geht (wäre
> zumindest in wien so). sorry aber wir hatten auch solche
> gleichungen auf der Uni und MUSSTEN vollständige induktion
> verwenden
In der Aufgabe stand doch:
" Gegeben sei die Gleichung [mm]S_{i}[/mm] = [mm]\bruch{i(i+1)}{2}[/mm] "
Also diese Gleichung (für [mm] i\in\IN) [/mm] ist gegeben. Das ist eine
Voraussetzung oder eine Definition, die hingenommen und
für den Beweis benützt, aber jedenfalls nicht selber bewiesen
werden soll. Man kann sie auch nicht beweisen.
> > In der zu zeigenden Ungleichung kommen die Terme [mm]S_{x+y}[/mm]
> > und
> > [mm]S_{x+y+1}[/mm] vor, wobei x und y für natürliche Zahlen
> > stehen.
> > Dass x+y und x+y+1 dann auch natürliche Zahlen sind,
> > muss
> > wohl so wenig neu bewiesen werden als etwa das
> > Distributiv-
> > gesetz.
>
> würde ich doch nicht ;) hab ja geschrieben "ja .. soetwas
> gibt man auch an dass man es tut ;)" bevor man mit einem
> beweis beginnt definiert bzw skizziert man sich ja einige
> sachen ;) (wie zb dass alle allgemein gültigen
> rechengesetze gelten / oder auch nicht)
>
> > Nach der Definition von [mm]S_i[/mm] ergibt sich dann:
> >
> > [mm]\ S_{x+y}\ =\ \bruch{(x+y)*(x+y+1)}{2}[/mm]
> >
> > [mm]\ S_{x+y+1}\ =\ \bruch{(x+y+1)*(x+y+2)}{2}[/mm]
> >
> > und [mm]\ S_{x+y+1}\ -\ S_{x+y}\ =\ \bruch{(x+y+1)}{2}\ *(\underbrace{(x+y+2)-(x+y)}_2)\ =\ x+y+1[/mm]
>
> >
> > Weil [mm]y\in\IN[/mm] , ist natürlich y>0 und x+y+1>x .
> > Also folgt [mm]\ S_{x+y+1}\ -\ S_{x+y}\ >\ x[/mm] oder
> > [mm]S_{x+y}+x
>
> auf das selbe würde ich auch kommen ;)
>
> > Vollständige Induktion ist für diesen Beweis überhaupt
> > nicht erforderlich, sondern nur die Anwendung der
> > "normalen" in [mm]\IN[/mm] gültigen Rechenregeln (für deren
> > ursprünglichen Beweis man eventuell schon auch
> > einmal vollständige Induktion eingesetzt hat).
>
> ich gebe dir schon recht dass die vollständige induktion
> nicht erforderlich sein muss bei diesem beispiel - jedoch
> würde ich auch ein bisschen drauf achten, das der herr
> kollege meinte ihr hauptthemengebiet sei zur zeit die
> vollständige induktion.
> solange der beweis richtig durchgeführt wird und solange
> das ergebnis passt sollte man meiner meinung nicht am
> "i-tüpfelchen" rumreiten
... allerdings hast du bisher jedenfalls keinen Beweis der
Ungleichung durch vollständige Induktion geliefert ...
LG Al-Chw.
|
|
|
| |
|
muss ich dir jetzt wirklich vorkauen was reverend schon längst (bzw ansatzweise) gemacht hat ? lol
|
|
|
| |
|
> muss ich dir jetzt wirklich vorkauen was reverend schon
> längst (bzw ansatzweise) gemacht hat ? lol
Musst du nicht, denn ich habe seinen Beitrag schon
längst gelesen. Er sagte dort zuerst ebenfalls, dass
der Beweis auch so (ohne V.I.) leicht zu führen
ist.
Dann gab er einen Tipp für einen allfälligen Induktions-
Beweis, den du aber jedenfalls nicht wirklich in die
Tat umgesetzt hast.
Im Übrigen möchte ich hier wirklich nicht streiten.
LG
|
|
|
| |
|
> Im Übrigen möchte ich hier wirklich nicht streiten.
dann verstehen ich die "Provokationen" nicht ganz, aber egal lassen wir's gut sein ;)
|
|
|
|
