Aufgabensammlung Mathematik: Vollständige Induktion

Vollständige Induktion

Summenformeln

Summe über ungerade Zahlen

Beweise, dass für alle $n\geq 1$ gilt:

$\sum _{k=1}^{n}(2k-1)=n^{2}$

Summe über Quadratzahlen

Beweise, dass für $n\in \mathbb {N} _{\geq 1}$ gilt:

$\sum _{k=1}^{n}k^{2}={{n\cdot (n+1)\cdot (2n+1)} \over 6}$

Summenformel über ungerade Quadratzahlen

Beweise, dass für $n\geq 1$ gilt:

$\sum _{k=1}^{n}(2k-1)^{2}={\frac {n\cdot (2n-1)\cdot (2n+1)}{3}}$

Summe über Kubikzahlen

Beweise, dass für $n\in \mathbb {N} _{\geq 1}$ gilt:

$\sum _{k=1}^{n}k^{3}=\left({\sum _{k=1}^{n}k}\right)^{2}=\left({{n\cdot (n+1)} \over 2}\right)^{2}$

Summenformel mit Induktionsvariable in der Summe

Beweise, dass für $n\geq 1$ gilt:

$\sum _{k=0}^{n-1}(n+k)\cdot (n-k)={{n\cdot (n+1)\cdot (4n-1)} \over 6}$

Teilbarkeit

Teilbarkeit durch 5

Beweise, dass $n^{5}-n$ für $n\in \mathbb {N} _{0}$ durch 5 teilbar ist.

Teilbarkeit durch 23

Beweise, dass $5^{2u}-2^{u}$ für $u\in \mathbb {N} _{0}$ durch 23 teilbar ist.

Teilbarkeit durch $2^{k+2}$

1. Beweise, dass $3^{(2^{k})}-1$ für $k\in \mathbb {N} _{\geq 1}$ durch $2^{k+2}$ teilbar ist.

2. Als zusätzliche Herausforderung kannst du versuchen, die folgende, allgemeinere Aussage zu beweisen:

$u^{(2^{k})}-1$ ist für ungerade $u\in \mathbb {N}$ und $k\in \mathbb {N} _{\geq 1}$ durch $2^{k+2}$ teilbar.

Diverses

Beweis einer Produktformel

Beweise, dass für $n\geq 2$ gilt:

$\prod _{k=2}^{n}\left(1-{\frac {2}{k\cdot (k+1)}}\right)={\frac {1}{3}}\cdot \left(1+{\frac {2}{n}}\right)$

Abschätzung der harmonischen Reihe nach oben

Beweise für alle natürlichen Zahlen $n\geq 1$ die folgende Ungleichung:

$\sum _{k=1}^{2^{n}-1}{1 \over k}\leq n$

Irrationalitätsbeweis

Zeige, dass für alle $n\in \mathbb {N} _{\geq 1}$ die folgende Aussageform $A(n)$ allgemeingültig ist:

$A(n):{\sqrt[{2^{n}}]{2}}$ ist irrational.

Beweis einer Identität

Zeige, dass für alle $n\in \mathbb {N} _{\geq 1}$ gilt: $\cos \left(n\pi \right)=\left(-1\right)^{n}$. Du darfst verwenden, dass $\cos(\pi )=-1$ und $\sin(\pi )=0$ ist.

Beweis einer Identität (2)

Zeige für alle $n\in \mathbb {N} _{\geq 1}$ die nachstehende Beziehung: $\sum _{k=1}^{n}{\arctan {\left({\frac {x}{1+k\left(k+1\right){x}^{2}}}\right)=\arctan {\left(\left(n+1\right)x\right)}}}-\arctan {\left(x\right)}.$

Allgemeine Bernoulli-Ungleichung

Zeige, dass für alle $n\in \mathbb {N} _{\geq 1}$ gilt:$\prod _{k=1}^{n}{\left(1+{a}_{k}\right)\geq 1+\sum _{k=1}^{n}{{a}_{k},\ mit\ {a}_{k}}}\geq -1,$ wobei alle ${a}_{k}$ das gleiche Vorzeichen aufweisen.

Anmerkung: Setzt man hier ${a}_{1}={a}_{2}=...={a}_{n}=x,$ so erhält man die "gewöhnliche" Bernoulli-Ungleichung ${\left(1+x\right)}^{n}\geq 1+nx\quad \left(x\geq -1\right).$

Finde den Fehler

Alle ungeraden Zahlen sind durch 2 teilbar

Behauptung: Alle ungeraden Zahlen sind durch 2 teilbar.

Beweis: Sei $n$ die $n$-te ungerade Zahl, welche durch 2 teilbar ist. Die $(n+1)$-te ungerade Zahl ist dann $n+2$ ist damit eine Summe aus zwei durch 2 teilbaren Summanden und damit wieder durch 2 teilbar. Aus der vollständigen Induktion folgt, dass alle ungeraden Zahlen durch 2 teilbar sind.

Es passt unendlich viel Sand in einen LKW

Behauptung: Es passen unendlich viele Sandkörner in einen LKW.

Induktionsanfang: Da ein Sandkorn sehr klein ist, passt auf jeden Fall ein Sandkorn in einen LKW.

Induktionsschritt: Gehen wir davon aus, dass $n$ Sandkörner im LKW sind. Da ein Sandkorn sehr, sehr klein ist im Vergleich zum Laderaum eines LKWs, passt ein zusätzliches Sandkorn auf jeden Fall in den LKW rein. Damit passen auch $n+1$ Sandkörner in einen LKW.

Daraus folgt, es passen beliebig viele Sandkörner in einen LKW (die Idee zu dieser Aufgabe stammt im Übrigen von der Mathekiste).

Auf einer Party haben alle denselben Namen

Behauptung: Auf einer Party mit $n\geq 1$ Gästen heißt jeder gleich.

Induktionsanfang: Wenn auf einer Party nur ein Gast ist, ist die Aussage wahr (weil es nur einen Namen gibt).

Induktionsschritt: Seien auf einer Party $n+1$ Gäste. Wir schicken einen raus. Dann sind auf dieser Party nur noch $n$ Gäste. Nach Induktionsvoraussetzung haben all diese $n$ Gäste den gleichen Namen. Nun holen wir den Gast, der draußen stand, wieder rein und schicken einen anderen Gast raus. Nun haben nach Induktionsvoraussetzung wieder alle den gleichen Namen. Also müssen alle $n+1$ Gäste den gleichen Namen haben.

Daraus folgt, dass alle Gäste auf einer Party gleich heißen.