Aufgabe 1
Sei $a_0=2$, $a_1=5$ und für $n\ge 2$ sei $a_n=5a_{n-1}-6a_{n-2}$.
Beweisen Sie $a_n=2^n+3^n$.
Tipp
Das ist eine Induktion des Typs $A(n-2), A(n-1)\RA A(n)$.
Daher braucht man zwei Startwerte für $n=2$.
Lösung
Anfang: $n = 0 : a_0 = 2 =2^0 + 3^0,\quad~ n = 1 : a_1 = 2+3 = 5$
Schritt: Vor: $a_{n-1} = 2^{n-1} + 3^{n-1},$ $ \quad a_{n-2}$ $ = 2^{n-2}
+ 3{^n-2}$
z.z. $a_n = 2^n + 3^n$
$a_n = 5a_{n-1} - 6a_{n-2} = 5(2^{n-1} + 3^{n-1}) - 6(2^{n-2}
+ 3^{n-2})$
$= 2^{n-2}(5 \cdot 2-6) + 3^{n-2}(5 \cdot 3-6) = $ $2^{n-2} \cdot 2^2
+ 3^{n-2} \cdot 3^2 = 2^n + 3^n$.
Aufgabe 2
Beweisen Sie mit
vollständiger Induktion (d.h. ohne Benutzung
von Summenformeln)
Für $n>1$ ist $\D \Sum_{k=1}^n k^2\ge \frac{n^3}{3}+1 $
Tipp
Anfang direkt nachrechnen, im Schritt eine Ungleichungskette verwenden.
Lösung
Anfang: $\D \sum_{k=1}^2 k^2=1+4=5$ $=\frac{15}{3}\ge \frac{8}{3}+1$
Schritt: Zeige $\D \sum_{k=1}^{n+1} k^2\ge \frac{(n+1)^3}{3}+1$
$\D \D \sum_{k=1}^{n+1} k^2\ge \frac{n^3}{3}+1 + (n+1)^2$
$\D=\frac{n^3+3n^3+3n+}{3}+(n+1)+\frac{2}{3}$
$\D\ge\frac{(n+1)^3}{3} +1$
Aufgabe 3
Beweisen Sie mit vollständiger Induktion
$\D \Sum_{k=1}^n \frac{1}{k^2}\le 2-\frac{1}{n}. $
Tipp
Der Anfang ist klar.
Im Schritt erst aufschreiben, wo man hinwill, dann mit Ungleichungskette nachweisen.
Lösung
Anfang: $\D \sum_{k=1}^1 \frac{1}{k^2}=1\le 2-\frac{1}{1}$
Zeige $\D \sum_{k=1}^{n+1} \frac{1}{k^2}\le 2-\frac{1}{n+1}$.
Nach Vorausetzung ist $\D \sum_{k=1}^{n+1} \frac{1}{k^2}\le 2-\frac{1}{n}+\frac{1}{(n+1)^2}$
Weiter: $\D =2-\frac{n^2+n+1}{n(n+1)^2}\le 2- \frac{n^2+n}{n(n+1)^2}$
$\D =2-\frac{1}{n+1}$.
Aufgabe 4
Beweisen Sie $\D \sum_{k=2}^n \frac{1}{{k\choose 2}}=2-\frac{2}{n}$
Tipp
Binomialkoeffizienten ausschreiben, dann ist der Rest völlig Standard.
Lösung
Mit $\D {k\choose 2}=\frac{k(k-1)}{2}$ ist die Behauptung
$\D \sum_{k=2}^n \frac{2}{k(k-1)}=2-\frac{2}{n}$.
Anfang $n=2$: $\D \sum_{k=2}^2 \frac{2}{k(k-1)}$ $\D \frac{2}{2\cdot1}=1$ $\D=2-\frac{2}{2}$ ok.
Schritt: Vorausgesetzt ist $\D \sum_{k=2}^n \frac{2}{k(k-1)}=2-\frac{2}{n}$.
Zu zeigen ist $\D \sum_{k=2}^{n+1} \frac{2}{k(k-1)}=2-\frac{2}{n+1}$.
Rechnung: $\D \sum_{k=2}^{n+1} \frac{2}{k(k-1)}$
$\D=\sum_{k=2}^n \frac{2}{k(k-1)}+\frac{2}{(n+1)n}
$ $\D \overset{\text{n.V.}}{=}2-\frac{2}{n}+ \frac{2}{(n+1)n}$ $\D=2-\frac{2(n+1)}{n(n+1)}+\frac{2}{n(n+1)}$ $\D=2-\frac{2(n+1-1)}{n(n+1)}$ $\D=
2-\frac{2}{n+1}$.
Aufgabe 5
Beweisen Sie: für $n\ge 1$ ist
$\D \Sum_{k=1}^n \frac{1}{k^2} \ge \frac{3}{2}-\frac{1}{n+1}$.
Tipp
Im Schritt eine Ungleichungskette verwenden und die entscheidende Ungleichung als Hilfsbehauptung separat beweisen.
Lösung
Anfang:
Zu zeigen ist $\D \Sum_{k=1}^1 \frac{1}{k^2} \ge \frac{3}{2}-\frac{1}{1+1}$.
Da beide Seiten den Wert $\D 1$ haben, ist das wahr.
Schritt $n\to n+1$:
Hilfsbehauptung (HB): es ist $\D -\frac{n}{(n+1)^2}\ge -\frac{1}{n+2}$.
Beweis: Vertauschen der Seiten ergibt
$\D \frac{1}{n+2}\ge \frac{n}{(n+1)^2}$.
Wenn man mit den Nennern multipliziert, steht da
$\D (n+1)^2\ge n(n+2)\LR n^2+2n+1\ge n^2+2n$, was wahr ist.
Beweis des Schritts:
Voraussetzung: $\D \Sum_{k=1}^n \frac{1}{k^2} \ge \frac{3}{2}-\frac{1}{n+1}$.
Behauptung: $\D \Sum_{k=1}^{n+1} \frac{1}{k^2} \ge \frac{3}{2}-\frac{1}{n+2}$.
Rechnung: $\D \Sum_{k=1}^{n+1} \frac{1}{k^2} $ $\D=\Sum_{k=1}^n \frac{1}{k^2} +\frac{1}{(n+1)^2}$ $\D \overset{\text{n.V.}}{\ge}\frac{3}{2}-\frac{1}{n+1}+\frac{1}{(n+1)^2}$ $\D =\frac{3}{2}-\frac{n}{(n+1)^2}$ $\D \overset{\text{HB}}{\ge} \frac{3}{2}-\frac{1}{n+2}$
