Einführung in das mathematische Arbeiten

Lösung für Aufgabe 2.5.6

Beweisen Sie die folgenden Identitäten für alle angegebenen $n\in\N$:

$\displaystyle\sum_{k=0}^n (3k-2)\,=\,\frac{(1+n)(3n-4)}{2}$, $n\geq 0$
$\displaystyle\sum_{k=1}^{n}k^{2}\,=\,\frac{n(n+1)(2n+1)}{6}$, $n\geq 1$
$(1+x)(1+x^{2})(1+x^{4})\dots(1+x^{2^{n-1}})(1+x^{2^{n}})\,=\, \frac{1-x^{2^{n+1}}}{1-x}$, $x\neq 1$, $n\geq 0$

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

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

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

$\Box$

Induktionsanfang: $n=1$ $$\sum_{k=1}^{1}k^2= 1= \frac{1(1+1)(2\cdot1+1)}6$$

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

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

Induktionsanfang: $n=0$ $$1+x=\frac{1-x^{2^{0+1}}}{1-x}=\frac{(1+x)(1-x)}{1-x}=1+x$$

Induktionsbehauptung: Für $x \neq 1$ und alle $n$ gelte $$(1+x)(1+x^2)(1+x^4)\dots(1+x^{2^{n-1}})(1+x^{2^n})=\frac{1-x^{2^{n+1}}}{1-x}$$

Induktionsschritt $n \to n+1$: \begin{eqnarray*} (1+x)(1+x^2)(1+x^4)\dots(1+x^{2^{n-1}})(1+x^{2^n})(1+x^{2^{n+1}})\;&=&\frac{1-x^{2^{n+1}}}{1-x}\cdot(1+x^{2^{n+1}})\\ &=&\frac{(1-x^{2^{n+1}})(1+x^{2^{n+1}})}{1-x}=\frac{1-x^{2(2^{n+1})}}{1-x}\\ &=&\frac{1-x^{2^{n+2}}}{1-x} \end{eqnarray*} $\Box$

ODER:

$$(1+x)(1+x^2)(1+x^4)\dots(1+x^{2^{n-1}})(1+x^{2^n})=\prod_{k=0}^{n} (1+x^{2^k})$$ Betrachte zur Herleitung den letzten Faktor des linken Produkts und überlege dann, die untere und obere Grenze für k.

Diese Umformung spart uns im Induktionsschritt einiges an Schreibarbeit: $$\prod_{k=0}^{n+1} (1+x^{2^k})=\prod_{k=0}^{n} (1+x^{2^k})(1+x^{2^{n+1}})=\frac{1-x^{2^{n+1}}(1+x^{2^{n+1}})}{1-x}=\frac{1-x^{2(2^{n+1})}}{1-x}$$