Umschlagbild
Wenn Sie das Buch noch nicht kennen, dann können Sie hier weitere Informationen finden.

Lösung für Aufgabe 2.5.5

Beweisen Sie die folgenden Identitäten für alle natürlichen $n\geq 1$:
  1. $\displaystyle\sum_{k=0}^n q^{-k}\,=\,\frac{q^{n+1}-1}{q^n(q-1)}$, $q\not=1$
  2. $\displaystyle\sum _{k=1} ^{n} (k^3+k) = \frac {n(n+1)(n^2+n+2)}{4}$
  3. $\displaystyle\sum _{k=2} ^{n} \frac {1} {k(k-1)} = \frac {n-1} {n} \quad$


1. Induktionsanfang: $n=0$ $$\sum_{k=0}^{0}q^{-k}=q^0= 1 = \frac{q-1}{q-1}.$$

Induktionsbehauptung: Für $q \neq 1$ und alle $n \geq 1$ gelte $$\sum_{k=0}^{n}q^{-k}=\frac{(q^{n+1})-1}{q^n(q-1)}.$$

Induktionsschritt $n \to n+1$: \begin{eqnarray*} \sum_{k=0}^{n+1}q^{-k} &=& \sum_{k=0}^{n}q^{-k}+q^{-n-1} = \frac{q^{n+1}-1}{q^n(q-1)}+q^{-n-1} = \frac{q^{n+1}-1+q^{-1}(q-1)}{q^n(q-1)} = \frac{q^{n+1}-1+q^{-1}(q-1)}{q^n(q-1)}\\ &=&\frac{q^{n+1}-1+q^0-q^{-1}}{q^n(q-1)}=\frac{q^{n+1}-q^{-1}}{q^n(q-1)}=\frac{q}{q-1}-\frac1{q^{n+1}(q-1)}=\frac{q^{n+2}-1}{q^{n+1}(q-1)} \end{eqnarray*} $\Box$

2. Induktionsanfang: $n=1$ $$\sum_{k=1}^{1}(k^3+k)=1+1= 2 = \frac{1(1+1)(1+1+2)}4.$$

Induktionsbehauptung: Für alle $n \geq 1$ gelte $$\sum_{k=1}^{n}k^3+k=\frac{n(n+1)(n^2+n+2)}4$$

Induktionsschritt $n \to n+1$: \begin{eqnarray*} \sum_{k=1}^{n+1}k^3+k&=&\sum_{k=1}^{n}(k^3+k)+(n+1)^3+(n+1)=\frac{n(n+1)(n^2+n+2)}4+(n+1)^3+(n+1)\\ &=&\frac{n(n+1)(n^2+n+2)+4(n+1)^3+4(n+1)}4=\frac{(n+1)(n^3+3n^2+4n+2n^2+6n+8)}4\\ &=&\frac{(n+1)(n+2)(n^2+2n+1+n+1+2)}4=\frac{(n+1)(n+2)((n+1)^2+(n+1)+2)}4 \end{eqnarray*} $\Box$

3. Induktionsanfang: $n=2$ $$\sum_{k=2}^{2}\frac1{k(k-1)}=\frac1{2\cdot1}= \frac12 = \frac{2-1}2.$$

Induktionsbehauptung: Für alle $n \geq 2$ gelte $$\sum_{k=2}^{n}\frac1{k(k-1)}=\frac{n-1}n$$

Induktionsschritt $n \to n+1$: $$\sum_{k=2}^{n+1}\frac1{k(k-1)}=\sum_{k=2}^{n}\frac1{k(k-1)}+\frac1{(n+1)n}=\frac{n-1}n + \frac1{(n+1)n}=\frac{(n-1)(n+1)+1}{n(n+1)}=\frac{n^2+1-1}{n(n+1)}=\frac n{n+1}$$ $\Box$

Eine alternative Lösung für das letzte Beispiel kommt ohne vollständige Induktion aus. Es gilt $$ \sum_{k=2}^n\frac1{k(k-1)} = \sum_{k=2}^n\frac1{k-1}-\frac1k = 1-\frac1n = \frac{n-1}n, $$ weil die zweite Summe eine Teleskopsumme ist.