# Algorithmen und Datenstrukturen: Blatt 0

## Aufgabe 3

Zu beweisen sind folgende Aussagen:
a) Für $n \in \mathbf{N}$ und $q \in \mathbf{R} \backslash\{1\}$ gilt:
$\sum_{k=0}^{n} q^k = \frac{1-q^{n+1}}{1-q}$.
Beweis per Induktion:
Induktionsanfang:
$n = 0 \Rightarrow \sum_{k=0}^{0} q^k = \frac{1-q^{0+1}}{1-q}$
$\Leftrightarrow q^0 = \frac{1-q}{1-q}$
$\Leftrightarrow 1 = 1$
Induktionsannahme: Die Aussage gilt für ein gegebenes n.
Induktionsschluss: $n \rightarrow n+1$
$\sum_{k=0}^{n+1} q^k = \frac{1-q^{n+2}}{1-q}$
$\Leftrightarrow q^{n+1}+\sum_{k=0}^{n} q^k = \frac{1-q^{n+2}}{1-q}$
$\Leftrightarrow q^{n+1}+\sum_{k=0}^{n} q^k =
\frac{1-q^{n+2}}{1-q}-q^{n+1} +q^{n+1}$
$\Leftrightarrow \sum_{k=0}^{n} q^k =\frac{1-q^{n+2}}{1-q}-q^{n+1}$
$\Leftrightarrow \sum_{k=0}^{n} q^k =
\frac{1-q^{n+2}}{(1-q)}-\frac{{q^{n+1}}*1-q}{1-q}$
$\Leftrightarrow \sum_{k=0}^{n} q^k =
\frac{1-q^{n+2}-{(q^{n+1}*(1-q))}}{1-q}$
$\Leftrightarrow \sum_{k=0}^{n} q^k =
\frac{1-q^{n+2}-{(q^{n+1}-q^{n+2})}}{1-q}$
$\Leftrightarrow \sum_{k=0}^{n} q^k =
\frac{1-q^{n+2}-{q^{n+1}+q^{n+2}}}{1-q}$
$\Leftrightarrow \sum_{k=0}^{n} q^k =
\frac{1-{q^{n+1}}}{1-q}$
Gilt nach Induktionsannahme. $\Box$

###### tags: `Algorithmen und Datenstrukturen` `Informatik` `Uni`