Teleskopsummen. Vollst. Induktion Σ (f(k) - f(k-1) ) = f(n) - f(0) und weitere Verwendung vom Ergebnis.

Question

ich habe ein Verständnisproblem bei der folgenden Aufgabe, bei der ich zuerst eine Vollständige Induktion machen soll und dann anschließend, wenn ich richtig verstehe, das Ergebnis von a) in b) und wiederum Ergebnis von b) in c) verwenden muss. Kann mir jemand erklären wie das funktioniert oder wie man das einsetzen muss? Oder vielleicht eine generelle "Methodik" nennen wie sowas funktioniert.

Ich verstehe absolut nicht wie genau das auszusehen hat... auf jedenfall darf ich bei b) keine vollständige Induktion benutzen, soll irgendwie von a) auf b) schließen. Mehr wurde mir auf Anfrage in der Übungsstunde nicht gesagt. :(   

Σ (f(k) - f(k-1) ) = f(n) - f(0)

Answer 1

a) ist ok.
b) Nimm f(k) = k^2
Dann ist f(k) - f(k-1) = k^2 - ( k^2 -2k + 1) = 2k-1 also genau der Summand, den du
für deine Summe brauchst.
Nach der Formel ist dann die Summe f(n) - f(0) = n^2 - 0 = n^2
c)     Erst mal für gerades n:
summe k = 1 bis n über k
=      summe i = 1 bis n/2 über 2i     +        summe i = 1 bis n/2 über 2i - 1 
=    (  summe i = 1 bis n/2 über 2i-1)       +n/2     +        summe i = 1 bis n/2 über 2i - 1 
und jetzt die Formel von oben mit n/2 statt n
=                 (n/2)^2                                 +  n/2                    +   (n^2)^2
=         2* n^2 / 4  +  n/2
=  n^2/2 + n/2    =    n*(n+1) / 2



            

Answer 2

Hi,
zu (a)
$$ \sum_{k=1}^n [ f(k) - f(k-1) ] = \sum_{k=1}^n f(k) -\sum_{k=1}^n f(k-1) = \sum_{k=1}^n f(k) - \sum_{k=0}^{n-1} f(k) = f(n) - f(0)  $$ weil sich sonst alle Terme aufheben. Summen obiger Art nennt man auch Teleskopsummen. Zum Beweis braucht man aber keine vollst. Induktion wie man sieht.

Zu (b)
Für die Funktion \( f(k) = k^2 \) gilt \( f(k) - f(k-1) = 2k - 1 \)
Aus (a) folgt dann
$$ \sum_{k=1}^n [2k - 1] =  \sum_{k=1}^n [ f(k) - f(k-1) ] =f(n) - f(0) = n^2 $$

Zu (c)
Aus (b) folgt $$ \sum_{k=1}^n [2k-1] = 2\sum_{k=1}^n k -n = n^2 $$ Daraus folgt
$$ \sum_{k=1}^n k = \frac{n^2+n}{2}= \frac{n(n+1)}{2}  $$

Comments

Hallo ullim,

mir ist immer noch nicht klar wie man darauf kommt,
wieso nimmt man bei b) einfach f(k) = k² an und lässt den Teil mit der Summe weg?
Und wieso kann man an der Stelle schon f(k) - f(k-1) = 2k - 1 schreiben?
(Wenn man das ausrechnet, wäre es doch f(k) - f(k-1) = k - k + 1 ?)

bei c) verstehe ich die Umformung in der ersten Zeile nicht so recht.
Wieso kann man da einfach die 2 rausziehen und 1 = n setzen?

Nebenbei:
Bei der Berechnung entsteht ja, wenn n = 5 ist, folgende Summe:

1 - 0 + 2 - 1 + 3 - 2 + 4 - 3 + 5 - 4

Oder habe ich da was missverstanden?
Falls nicht, welchen Sinn hat diese Berechnung überhaupt?

---

Hi,
also bei (b) gilt ja \( f(k) - f(k-1) = 2k - 1 \) wenn man \( f(k) = k^2 \) wählt. Ich denke das ist klar und kann man durch nachrechnen bestätigen.
Wegen (a) gilt $$ (1) \quad \sum_{k=1}^n \left[ f(k) - f(k-1) \right] = f(n) - f(0) $$ für jede Funktion \( f \).
Jetzt setzt man die speziell gewählte Funktion in (1) ein, erhält man natürlich ebenfalls als Ergebnis \( f(n) -f(0) \)
Für die spezielle Funktion \( f(k) = k^2 \) folgt damit \( f(n) - f(0) = n^2 -0 = n^2 \)

Bei (c) gilt
Die \( 2 \) kann man aus der Summe ziehen, weil sie ja nicht von \( k \) abhängt. Also sieht das so aus
$$ n^2 = \sum_{k=1}^n [2k-1] = 2\sum_{k=1}^n k - \sum_{k=1}^n 1 $$ Der Ausdruck \( \sum_{k=1}^n 1  \) wird zu \( \sum_{k=1}^n 1 = n \) weil man n-mal die \( 1 \) aufsummiert.
Insgesamt ergibt sich also das ,was ich vorher schon geschrieben habe.

---

Könnten Sie mir doch nochmal den Zwischenschritt zeigen, von f(k) - f(k-1) zu 2k - 1?

Müsste man nicht 2k + 1 erhalten? Weshalb ist die 1 noch negativ, wenn ich das ausrechne bekomme ich f(k) - f(k-1) = k - (k-1) = k - k + 1 und weil k = k^2 immer pos. ist, sagt man dann k + k + 1 = 2k + 1... oder wie wird das ausgerechnet? Also irgendwie verstehe ich das nicht so ganz. :(

Achso nun ist mir der Fehler während ich schrieb aufgefallen... man muss (k-1)^2 nehmen (warum eigentlich?) und nicht bloß das k...

Vielen lieben Dank für die tolle Hilfe, ich hoffe das ich da nun mehr durchblicke, irgendwie ist das schon sehr gewöhnungsbedürftig sich da hineinzudenken. :/

---

$$  f(k) - f(k-1) = k^2 - (k-1)^2 = k^2 - (k^2 - 2k + 1) = k^2 -k^2 +2k -1 = 2k -1 $$