04 Die natürlichen Zahlen II

Tipp: Es ist sinnvoll, die Aussage in folgende Formel zu bringen: $$\begin{array}{r}\sum _{k=1}^n(2k-1)=n^2.\end{array}$$

$$\begin{array}{r}\sum _{k=1}^n(2k-1)=n^2.\end{array}$$ Beweis mit Induktion nach $n$:
Der Induktionsanfang mit $n=n$ ist klarerweise richtig: $1=1^2.$
Bemerkung: Ganz gewiefte Mathematiker beginnen manchmal auch mit $n=0$, wobei wir dann eine leere Summe (von $k=1$ bis $0$) hätten, deren Wert natürlich $0$ ist. Klarerweise gilt $0=0^2$, der Induktionsanfang ist also auch hier richtig. Induktionsschritt $n⟶n+1$ (der wie gesagt auch für $n=0$ gehen würde): $$\begin{array}{r}\sum _{k=1}^{n+1}(2k-1)=(2n+1)+\sum _{k=1}^n(2k-1)=(2n+1)+\underset{IndV}{\underbrace{n^2}}=(n+1{)}^2.\end{array}$$ Fertig!

Induktionsanfang $n=0$: Die linke Seite ergibt auch $0$.
Induktionsschritt n \longrightarrow n + 1 (beachten Sie, dass die Rechnung auch für $n=0$ funktioniert): $$\begin{array}{r}6\cdot \sum _{k=1}^{n+1}{k}^2=6(n+1{)}^2+6\cdot \sum _{k=1}^n{k}^2=6(n+1{)}^2+\underset{IndV}{\underbrace{n(n+1)(2n+1)}}\end{array}$$ $$\begin{array}{r}=(n+1)(6(n+1)+n(2n-1))=(n+1)(6n+6+n(2n+3)-2n)\end{array}$$ $$\begin{array}{r}=(n+1)(4n+6+n(2n+3))=(n+1)(2(2n+3)+n(2n+3))\end{array}$$ $$\begin{array}{r}=(n+1)(n+2)(2n+3).\end{array}$$ Das ist genau die Formel für $n+1.$

Auch hier kommen Sie mit vollständiger Induktion ans Ziel. Die Aussage $b_n\le 2^n$ stimmt offenbar für $n=0$ und $n=1$ (Induktionsanfang).
Induktionsschritt $n⟶n+1$ (ab $n=1$ möglich): $$\begin{array}{r}{b}_{n+1}=b_n+b_{n-1}\le 2^n+2^{n-1}\le 2\cdot 2^n=2^{n+1}.\end{array}$$ Das war also nicht schwer. Wie sieht es aber mit einer vernünfigen Schranke nach unten aus? Also eine Abschätzung $$\begin{array}{r}{b}_n\ge f(n).\end{array}$$ Auch die gibt es, allerdings ist sie nicht ganz so leicht zu finden. Wenn Sie schon mit irrationalen Quadratwurzeln jonglieren können, dann sei dieser Vorgriff auf ein späteres Kapitel erlaubt und Sie können gerne ein wenig probieren.

Kleiner Tipp: Bedenken Sie, dass folgende Gleichung gilt: $$\begin{array}{r}{b}_{n+2}=bn+1+b_n\ge 2\cdot b_n.\end{array}$$

Durch ein wenig Probieren finden Sie weitere Zusammenhänge, die einen Hinweis auf die Lösung geben. So ist zum Beispiel $$\begin{array}{r}{b}_{n+4}=b_{n+3}+b_{n+2}\ge 2^2\cdot b_n,\\ b_{n+6}=b_{n+5}+b_{n+4}\ge 2^3\cdot b_n,\\ b_{n+8}=b_{n+7}+b_{n+6}\ge 2^4\cdot b_n,\\ b_{n+10}=b_{n+9}+b_{n+8}\ge 2^5\cdot b_n,\end{array}$$ Der Exponent bel der $2$ auf der rechten Seite wächst also genau halb so schnell wie die Zahl, die wir auf der linken Seite im Index zu $n$ addieren. Ein erstaunlicher Zusammenhang. Nun kommt der kleine Vorgriff auf später: Dieses halb so schnelle Wachsen können wir ausgleichen, indem wir auf der rechten Seite statt der $2$ als Basis $\sqrt{2}$ wählen. Denn es ist zum Beispiel $2^2={\sqrt{2}}^4$ oder $2^3={\sqrt{2}}^6.$ Dies führt uns schließlich zu der Vermutung, dass stets $$\begin{array}{r}{b}_n\ge {\sqrt{2}}^n\end{array}$$ ist. Auch das ist einfach mit vollständiger Induktion zu erledigen, der Induktionsanfang für $n<1$ist klar.
Induktionsschritt $n⟶n+1$(ab $n=1$ möglich): $$\begin{array}{r}{b}_{n+1}=b_n+b_{n-1}\ge {\sqrt{2}}^{"n"}+{\sqrt{2}}^{n-1}\ge 2\cdot {\sqrt{2}}^{n-1}={\sqrt{2}}^{n+1}.\end{array}$$ Damit gibt es tatsächlich die schöne Einschließung $$\begin{array}{r}{\sqrt{2}}^n\le b_n\le 2^n\end{array}$$ für diese Folge. Man sagt auch, sie hat ein exponentielles Wachstum.
Das spielt übrigens eine gewichtige Rolle bei der Untersuchung der Laufzeit eines bekannten Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier natürlicher Zahlen doch das würde hier zu weit gehen, vielleicht fragen Sie einfach mal Ihren Informatik-Professor...
Glückwunsch, Sie haben es geschafft! Viel Spaß beim nächsten Kapitel.