Induktion/Summe < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:41 Do 19.01.2012 | | Autor: | sissile |
| Aufgabe | | [mm] \frac{a^{n} - b^{n}}{a-b} [/mm] = [mm] \sum_{k=0}^{n-1} a^k [/mm] * [mm] b^{n-1-k} [/mm] |
Induktionsanfang für n =1
1=1 gilt
Induktionsannahme: [mm] \frac{a^{n} - b^{n}}{a-b} [/mm] = [mm] \sum_{k=0}^{n - 1} a^k [/mm] * [mm] b^{n-1-k}
[/mm]
ZuZeigen: [mm] \frac{a^{n+1} - b^{n+1}}{a-b} [/mm] = [mm] \sum_{k=0}^{n} a^k [/mm] * [mm] b^{n-1-k}
[/mm]
Induktionsschritt:
[mm] \sum_{k=0}^{n} a^k [/mm] * [mm] b^{n-1-k} [/mm] = [mm] \sum_{k=0}^{n-1} a^k [/mm] * [mm] b^{n-1-k} [/mm] + [mm] a^n [/mm] * [mm] b^{n-1-n} [/mm] = [mm] \frac{a^{n} - b^{n}}{a-b} +a^n [/mm] * [mm] b^{-1} =\frac{a^{n} - b^{n}}{a-b} +\frac{(a-b)*a^n * b^{-1}}{a-b} [/mm] = [mm] \frac{a^n - b^n + a^{n+1}/b - b*a^n/b}{a-b}=\frac{b*a^n/b - b^{n+1}/b + a^{n+1}/b - b*a^n/b}{a-b} [/mm] = [mm] \frac{-b^{n+1} + a^{n+1}}{b*(a-b)}
[/mm]
Wo ist der Fehler, oder gehe ich da ganz falsch vor?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:40 Do 19.01.2012 | | Autor: | Walde |
Hi sissile,
> [mm]\frac{a^{n} - b^{n}}{a-b}[/mm] = [mm]\sum_{k=0}^{n-1} a^k[/mm] * [mm]b^{n-1-k}[/mm]
> Induktionsanfang für n =1
> 1=1 gilt
> Induktionsannahme: [mm]\frac{a^{n} - b^{n}}{a-b}[/mm] = [mm]\sum_{k=0}^{n - 1} a^k[/mm] * [mm]b^{n-1-k}[/mm]
> ZuZeigen: [mm]\frac{a^{n+1} - b^{n+1}}{a-b}[/mm] = [mm]\sum_{k=0}^{n} a^k[/mm] * [mm]b^{n\red{-1}-k}[/mm]
Ich hab nur bis hierhin gelesen. In der Summe muß es dann doch auch [mm] b^{n-k} [/mm] heißen.
LG walde
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:44 Do 19.01.2012 | | Autor: | sissile |
Das würde ein Problem lösen.,
Aber warum !?
Ich hab doch schon meine Summe geändert, warum noch auch eine Hochzahl?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:53 Do 19.01.2012 | | Autor: | Walde |
Ei, überall wo ein n steht, muß ein n+1 hin. Ansonsten wäre doch das letzte Summenglied auch [mm] a^n*b^{-1 }, [/mm] das kann doch hier nicht sein.
LG walde
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:21 Fr 20.01.2012 | | Autor: | sissile |
Aber wir haben doch die Angabe für die Summe [mm] \summe_{k=0}^{n-1}
[/mm]
Dann müssen wir doch im Induktionsschritt von n-1 -> n schließen?
Ist nun zu zeigen:
$ [mm] \frac{a^{n+1} - b^{n+1}}{a-b} [/mm] $ = $ [mm] \sum_{k=0}^{n} a^k [/mm] $ * $ [mm] b^{n-k} [/mm] $
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 01:54 Fr 20.01.2012 | | Autor: | Walde |
> Aber wir haben doch die Angabe für die Summe
> [mm]\summe_{k=0}^{n-1}[/mm]
> Dann müssen wir doch im Induktionsschritt von n-1 -> n schließen?
Nein, deine Induktion hast du doch mit:
Induktionsannahme (,d.h. es gelte für n): [mm] \frac{a^{n} - b^{n}}{a-b}=... [/mm] angefangen und nicht für n-1, also mit [mm] \frac{a^{n-1} - b^{n-1}}{a-b}
[/mm]
> Ist nun zu zeigen:
> [mm]\frac{a^{n+1} - b^{n+1}}{a-b}[/mm] = [mm]\sum_{k=0}^{n} a^k[/mm] * [mm]b^{n-k}[/mm]
Na klar, hast du doch auch bei "zu zeigen" hingeschrieben. Überall wo n stand n+1 geschrieben. Nur innerhalb der Summe nicht, aber da muß man es auch. Überall halt 
Kuck mal, du hast doch [mm] \frac{a^{n} - b^{n}}{a-b}=\sum_{k=0}^{n - 1} a^k *b^{n-1-k}=a^0*b^{n-1}+\ldots+a^{n-1}*b^0
[/mm]
und wenn du n durch n+1 ersetzt muß es heißen
[mm] \frac{a^{n+1} - b^{n+1}}{a-b}=a^0*b^{n}+\ldots+a^{n}*b^0 [/mm] und das ist
[mm] =\sum_{k=0}^{n} a^k *b^{n-k}
[/mm]
Alles klar ?
LG walde
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 02:00 Fr 20.01.2012 | | Autor: | sissile |
ZZ:
> $ [mm] \frac{a^{n+1} - b^{n+1}}{a-b} [/mm] $ = $ [mm] \sum_{k=0}^{n} a^k [/mm] $ * $ [mm] b^{n-k} [/mm] $
Induktionsschritt:
[mm] =\sum_{k=0}^{n} a^k \cdot{}b^{n-k} =\sum_{k=0}^{n-1} a^k \cdot{}b^{n-1-k} [/mm] $ +$ [mm] a^n b^0
[/mm]
= [mm] \frac{a^n-b^n}{a-b} [/mm] + [mm] a^n
[/mm]
= [mm] \frac{a^{n+1}-b^n*a^n}{a-b} [/mm]
Habe ich nun was falsch gemacht, dass ich nicht auf das was zu zeigen ist komme?
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:08 Fr 20.01.2012 | | Autor: | Walde |
> ZZ:
> > [mm]\frac{a^{n+1} - b^{n+1}}{a-b}[/mm] = [mm]\sum_{k=0}^{n} a^k[/mm] * [mm]b^{n-k}[/mm]
> Induktionsschritt:
> [mm]=\sum_{k=0}^{n} a^k \cdot{}b^{n-k} =\sum_{k=0}^{n-1} a^k \cdot{}b^{n\red{-1}-k}[/mm] [mm]+[/mm] [mm]a^n b^0[/mm]
> Habe ich nun was falsch gemacht, dass ich nicht auf das was
> zu zeigen ist komme?
Ja, wenn du das letzte Glied abtrennst, darfst du innerhalb der Summe, nicht einfach die Darstellung verändern. Da verändert sich in der Tat nur bis wohin die Summe läuft. Wenn du ein -1 in den Exponenten haben willst, klammere ein b aus.
LG walde
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:32 Fr 20.01.2012 | | Autor: | sissile |
$ [mm] =\sum_{k=0}^{n} a^k \cdot{}b^{n-k} =\sum_{k=0}^{n-1} a^k \cdot{}b^{n-k} [/mm] + [mm] a^n b^0 [/mm] $ = b *( [mm] \sum_{k=0}^{n-1} a^k \cdot{}b^{n-k-1} [/mm] + [mm] a^n b^{-1} [/mm] )= b * ( [mm] \frac{a^{n} - b^{n}}{a-b}+a^n b^{-1})= \frac{b*a^{n} - b^{n+1}}{a-b} [/mm] + [mm] a^n =\frac{b*a^{n} - b^{n+1}+a^{n+1}-b*a^n}{a-b} [/mm] = $ [mm] \frac{a^{n+1} - b^{n+1}}{a-b} [/mm] $
DANKE ;))
LG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:40 Fr 20.01.2012 | | Autor: | Walde |
Gern geschehen 
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:18 Do 19.01.2012 | | Autor: | Marcel |
Hallo,
> [mm]\frac{a^{n} - b^{n}}{a-b}[/mm] = [mm]\sum_{k=0}^{n-1} a^k[/mm] *
> [mm]b^{n-1-k}[/mm]
hier braucht man nicht unbedingt Induktion. Man kann es einfach nachrechnen:
[mm] $$(a-b)*\sum_{k=0}^{n-1}a^k b^{n-1-k}=\left(a*\sum_{k=0}^{n-1}a^kb^{n-1-k}\right)-\left(b*\sum_{k=0}^{n-1}a^{k}b^{n-1-k}\right)=\left(\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}\right)-\sum_{k=0}^{n-1}a^kb^{n-k}=\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-\sum_{k=0}^{n-1}a^kb^{n-k}\,.$$
[/mm]
(Anstatt zu schreiben, "einen Indexshift zu machen" habe ich hier einfach die Laufvariable sozusagen passend substituiert - [mm] $m:=k+1\,.$ [/mm] Wenn [mm] $k\,$ [/mm] alle Werte aus [mm] $\{0,\;1,\;\ldots,n-1\}$ [/mm] durchläuft, dann [mm] $m\,$ [/mm] alle aus [mm] $\{1,\;2,\;\ldots,\;n\}\,.$ [/mm] Genaugenommen ist das aber nur das, was man beim Indexshift macht, nochmal in einzelnen Schritten hingeschrieben. Also eigentlich ist das genau der "Indexshift".)
Und jetzt schau' mal genau hin, oder anders gesagt:
Wende oben die "Zerlegungen der Art" [mm] $\sum_{m=1}^n x_m=\left(\sum_{m=1}^{n-1}x_m\right)+x_n$ [/mm] und [mm] $\sum_{k=0}^{n-1}y_k=y_0+\sum_{k=1}^{n-1}y_k\,$ [/mm] an.
P.S.:
Deinen Induktionsbeweis solltest Du natürlich dennoch zu Ende führen!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:44 Fr 20.01.2012 | | Autor: | sissile |
Hallo
> $ [mm] (a-b)\cdot{}\sum_{k=0}^{n-1}a^k b^{n-1-k}=\left(a\cdot{}\sum_{k=0}^{n-1}a^kb^{n-1-k}\right)-\left(b\cdot{}\sum_{k=0}^{n-1}a^{k}b^{n-1-k}\right)=\left(\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}\right)-\sum_{k=0}^{n-1}a^kb^{n-k}=\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-\sum_{k=0}^{n-1}a^kb^{n-k}\,. [/mm] $
> Wende oben die "Zerlegungen der Art"
[mm] \left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-b^n-\sum_{k=1}^{n-1}a^kb^{n-k}\,. [/mm]
Wie gehts nun weiter?
Liebe Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:33 Fr 20.01.2012 | | Autor: | Marcel |
Hallo,
> Hallo
> > [mm](a-b)\cdot{}\sum_{k=0}^{n-1}a^k b^{n-1-k}=\left(a\cdot{}\sum_{k=0}^{n-1}a^kb^{n-1-k}\right)-\left(b\cdot{}\sum_{k=0}^{n-1}a^{k}b^{n-1-k}\right)=\left(\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}\right)-\sum_{k=0}^{n-1}a^kb^{n-k}=\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-\sum_{k=0}^{n-1}a^kb^{n-k}\,.[/mm]
>
> > Wende oben die "Zerlegungen der Art"
>
> [mm]\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-b^n-\sum_{k=1}^{n-1}a^kb^{n-k}\,.[/mm]
ich hatte extra "zwei" Zerlegungen hingeschrieben. Also mach' ich mal die nächste für Dich:
[mm] $$\ldots=]\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-b^n-\sum_{k=1}^{n-1}a^kb^{n-k}=\left(\left(\blue{\sum_{m=1}^{n-1}a^{m}b^{n-m}}\right)+a_n\right)-b^n-\blue{\sum_{k=1}^{n-1}a^kb^{n-k}}\,.$$
[/mm]
Fällt Dir was auf? (Okay, nachdem ich es so deutlich markiert habe, muss ich ja schon fast davon ausgehen...)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:45 Fr 20.01.2012 | | Autor: | sissile |
> [mm]\ldots=]\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-b^n-\sum_{k=1}^{n-1}a^kb^{n-k}=\left(\left(\blue{\sum_{m=1}^{n-1}a^{m}b^{n-m}}\right)+a^{n} \right)-b^n-\blue{\sum_{k=1}^{n-1}a^kb^{n-k}}\,.[/mm]
>
> Fällt Dir was auf? (Okay, nachdem ich es so deutlich
> markiert habe, muss ich ja schon fast davon ausgehen...)
Naja das die beiden Summen fast gleich sind, außer die Laufvariable.
Einmal m =k+1
und einmal k
Es müsse ja [mm] a^n [/mm] - [mm] b^n [/mm] rauskommen, aber es sind doch nicht ganz genau die selben Summen?Um sie weg-zu-subtrahieren.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:53 Fr 20.01.2012 | | Autor: | Walde |
Wie die Laufvariable heißt, ist egal. Um das einzusehen, mußt du nur mal paar Summenglieder hinschreiben, dann siehts du, dass das gleiche da steht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:01 Fr 20.01.2012 | | Autor: | Marcel |
Hallo sissile,
> >
> [mm]\ldots=]\left(\sum_{m=1}^{n}a^{m}b^{n-m}\right)-b^n-\sum_{k=1}^{n-1}a^kb^{n-k}=\left(\left(\blue{\sum_{m=1}^{n-1}a^{m}b^{n-m}}\right)+a^{n} \right)-b^n-\blue{\sum_{k=1}^{n-1}a^kb^{n-k}}\,.[/mm]
>
> >
> > Fällt Dir was auf? (Okay, nachdem ich es so deutlich
> > markiert habe, muss ich ja schon fast davon ausgehen...)
>
> Naja das die beiden Summen fast gleich sind, außer die
> Laufvariable.
sie sind gleich. Die Laufvariable ist doch egal (wie mein Vorredner schon andeutete).
> Einmal m =k+1
> und einmal k
> Es müsse ja [mm]a^n[/mm] - [mm]b^n[/mm] rauskommen, aber es sind doch nicht
> ganz genau die selben Summen?Um sie weg-zu-subtrahieren.
Warum nicht? Ohje, wenn Dir das nicht klar ist, wirst Du niemals Schleifen programmieren können - ohne verwirrt zu sein. Aber nun gut, wir klären das nochmal - anscheinend hast Du das vergessen oder ihr habt einfach die einfachsten Übungsaufgaben/Hinweise in der Vorlesung weggelassen:
Mach' Dir mal klar, dass etwa
[mm] $$\sum_{k=1}^5 a_k=a_1+a_2+a_3+a_4+a_5$$
[/mm]
ist.
Was macht man da (iterativ)? Man setzt $k=1$ und schreibt [mm] $a_1\,,$ [/mm] dann wird [mm] $k=2\,$ [/mm] gesetzt und [mm] $a_2$ [/mm] zu [mm] $a_1$ [/mm] dazuaddiert, [mm] $a_1+a_2\,,$ [/mm] nun wird [mm] $k=3\,$ [/mm] gesetzt und dazuaddiert: [mm] $a_1+a_2+a_3$ [/mm] ... bis man schlussendlich bei [mm] $a_1+a_2+a_3+a_4+a_5$ [/mm] ankommt.
Bei
[mm] $$\sum_{\ell=1}^5 a_\ell=a_1+a_2+a_3+a_4+a_5$$
[/mm]
ist das genau das gleiche - nur heißt die Variable, wo man was einsetzt, anders - [mm] $\ell$ [/mm] - aber sie übernimmt komplett die Rolle von [mm] $k\,.$ [/mm]
Du kannst auch
[mm] $$\sum_{peter=1}^5 a_{peter}=a_1+a_2+a_3+a_4+a_5$$
[/mm]
schreiben, wenn Deine Laufvariable [mm] $peter\,$ [/mm] heißt.
Was man beim Summenzeichen beachten sollte, ist, dass es bei einer endlichen Summe (d.h. bei endlichen vielen (rellen oder komplexen) Summanden) nicht auf die Reihenfolge der Summanden ankommt (allgemeiner kann man das so sagen, wenn die "Addition" das Distributiv- und das Kommutativgesetz erfüllt):
Es wäre etwa
[mm] $$\sum_{k=1}^5 a_k=\sum_{m=0}^4 a_{5-m}=a_1+a_2+a_3+a_4+a_5\,,$$
[/mm]
auch, wenn man "iterativ" erstmal
[mm] $$\sum_{m=0}^4 a_{5-m}=a_5+a_4+a_3+a_2+a_1$$
[/mm]
da stehen hat. Aber das ist das gleiche wie [mm] $a_1+a_2+a_3+a_4+a_5\,.$
[/mm]
Allgemeiner:
[mm] $$\sum_{k=1}^n a_k=\sum_{m=1}^n a_{\phi(m)}$$
[/mm]
für eine Bijektion [mm] $\phi: \{1,2,3,4,\ldots,n\} \to \{1,2,3,4,\ldots,n\}\,.$ [/mm] (Da steht eine Bijektion einer endlichen Menge in sich selbst.)
Daher macht es hier auch Sinn, das ganze so zu schreiben
[mm] $$\sum_{t \in \{1,2,3,4,5\}}a_t=a_1+a_2+a_3+a_4+a_5\,.$$
[/mm]
(Bei unendlichen Reihen muss man da i.a. vorsichtiger sein. )
Denk einfach ein wenig drüber nach. Und vielleicht hast Du ja minimale Programmiererfahrung. Was wäre denn der Unterschied, wenn da stünde
"
int s=0;
for (int i=1, i < 9,i++)
s=s+i;
"
verglichen mit
"
int s=0;
for (int k=1, k < 9,k++)
s=s+k;
"
Würden da verschiedene Ergebnisse s entstehen?
(P.S.: Ich bin nun nicht so der Programmierer, aber ich denke, so oder jedenfalls so ähnlich sähe das in C aus. Lies' es meinetwegen im Sinne eines Pseudocodes.)
Gruß,
Marcel
|
|
|
|
