Aimathic – Vollständige Induktion – Kostenlose Arbeitsblätter

Vollständige Induktion

Klicken Sie auf Aufgaben, um sie zum Drucken auszuwählen.

Schwierigkeit: 1 – 5

43792712

Eine Schülerin untersucht die Behauptung \(1+3+5+\dots +(2n-1)=n^2\) für \(n\ge 1\). Sie erhält: <table><tr><th>\(n\)</th><th>linke Seite</th><th>rechte Seite</th></tr><tr><td>\(1\)</td><td>\(1\)</td><td>\(1\)</td></tr><tr><td>\(2\)</td><td>\(4\)</td><td>\(4\)</td></tr><tr><td>\(3\)</td><td>\(9\)</td><td>\(9\)</td></tr><tr><td>\(4\)</td><td>\(16\)</td><td>\(16\)</td></tr><tr><td>\(5\)</td><td>\(25\)</td><td>\(25\)</td></tr></table> Erkläre, warum dies noch kein Beweis für alle \(n\ge 1\) ist, und formuliere die beiden zusätzlich nötigen Beweisschritte.

Denkanstöße

- Überlege, was endlich viele Beispiele über unendlich viele Fälle aussagen können. - Trenne den ersten Fall vom Übergang auf den jeweils nächsten Fall.

Lösung

1. Die fünf Rechnungen bestätigen die Behauptung nur für fünf einzelne Werte; daraus folgt keine Aussage über alle natürlichen Zahlen. 2. Im Induktionsanfang ist die Behauptung für den ersten zulässigen Wert zu zeigen. 3. Im Induktionsschritt ist für ein beliebiges \(k\) aus der Annahme \(1+3+\dots +(2k-1)=k^2\) die Aussage \(1+3+\dots +(2k+1)=(k+1)^2\) herzuleiten.

Antwort

Die Tabelle liefert nur Beispiele. Nötig sind ein gültiger Induktionsanfang und der allgemeine Schluss von \(k\) auf \(k+1\).

43792812

Beweise durch vollständige Induktion, dass für alle \(n\ge 1\) gilt: \(2+4+6+\dots +2n=n(n+1)\).

Denkanstöße

- Prüfe zuerst den kleinsten zulässigen Wert. - Vergleiche die Summe für zwei aufeinanderfolgende Anzahlen von Summanden.

Lösung

1. Für \(n=1\) gilt \(2=1\cdot 2\). 2. Es gelte \(2+4+\dots +2k=k(k+1)\). Dann ist \(2+4+\dots +2k+2(k+1)=k(k+1)+2(k+1)=(k+1)(k+2)\). Damit gilt die Formel für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) ist \(2+4+\dots +2n=n(n+1)\).

43792912

In einem angeblichen Induktionsbeweis steht: „Wir nehmen an, dass die Behauptung bereits für \(k+1\) gilt. Daraus folgt unmittelbar die Behauptung für \(k+1\).“ Benenne den Fehler und formuliere die korrekte Induktionsvoraussetzung.

Denkanstöße

- Prüfe, ob im Argument bereits das angenommen wird, was erst gezeigt werden soll. - Achte auf den Unterschied zwischen dem aktuellen und dem nächsten Index.

Lösung

1. Die zu beweisende Aussage für \(k+1\) wird bereits vorausgesetzt; das ist ein Zirkelschluss. 2. Korrekt darf nur angenommen werden, dass die Behauptung für ein beliebiges \(k\) gilt. 3. Aus dieser Annahme muss anschließend die Behauptung für \(k+1\) folgen.

Antwort

Der Beweis ist zirkulär. Die Induktionsvoraussetzung muss die Aussage für \(k\), nicht für \(k+1\), annehmen.

43793312

Für den Beweis „\(n(n+1)\) ist für alle \(n\ge 1\) gerade“ werden drei mögliche Induktionsvoraussetzungen vorgeschlagen: A: \(k(k+1)\) ist gerade. B: \((k+1)(k+2)\) ist gerade. C: \(k\) ist gerade. Wähle die passende Voraussetzung und führe den Induktionsschritt aus.

Denkanstöße

- Die Voraussetzung muss dieselbe Aussage wie die Behauptung enthalten, nur mit einem festen Index. - Schreibe den Ausdruck für den nächsten Index als alten Ausdruck plus Ergänzung.

Lösung

1. Passend ist A, denn sie ist die Behauptung für den Index \(k\). 2. Es gilt \((k+1)(k+2)=k(k+1)+2(k+1)\). 3. Der erste Summand ist nach Voraussetzung gerade, der zweite ist ein Vielfaches von \(2\); daher ist auch die Summe gerade.

Antwort

Richtig ist A. Aus \((k+1)(k+2)=k(k+1)+2(k+1)\) folgt die Geradheit für \(k+1\).

43793412

Eine Aussage lautet für \(n\ge 2\): \(2+3+\dots +n=\frac{n(n+1)}{2}-1\). Ein Schüler beginnt den Induktionsbeweis mit \(n=1\). Erkläre, warum dieser Anfang nicht zur angegebenen Aussage passt, und gib den korrekten Induktionsanfang an.

Denkanstöße

- Achte darauf, ab welchem Wert die Behauptung überhaupt gelten soll. - Setze den kleinsten zulässigen Wert auf beiden Seiten ein.

Lösung

1. Die Aussage ist erst ab \(n=2\) formuliert; ein Nachweis bei \(n=1\) liegt außerhalb des angegebenen Bereichs. 2. Der korrekte Anfang ist \(n=2\): Links steht \(2\), rechts \(\frac{2\cdot 3}{2}-1=2\). 3. Von diesem Start aus kann der Schluss für alle \(n\ge 2\) weitergeführt werden.

Antwort

Der Induktionsanfang muss bei \(n=2\) liegen; dort sind beide Seiten gleich \(2\).

43793712

Die Folge ist durch \(a_1=4\) und \(a_{n+1}=a_n+3\) definiert. Beweise durch vollständige Induktion die explizite Formel \(a_n=3n+1\).

Denkanstöße

- Vergleiche die rekursive Veränderung mit der Veränderung der vermuteten Formel. - Prüfe zuerst, ob die Formel den Anfangswert trifft.

Lösung

1. Für \(n=1\) gilt \(a_1=4=3\cdot 1+1\). 2. Es gelte \(a_k=3k+1\). Dann ist \(a_{k+1}=a_k+3=3k+4=3(k+1)+1\). 3. Somit gilt die Formel für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) gilt \(a_n=3n+1\).

43793912

Ein „Beweis“ behauptet: Jede natürliche Zahl sei gleich ihrer Nachfolgerin. Aus \(k=k+1\) werde durch Addition von \(1\) die Gleichung \(k+1=k+2\). Wo liegt der Fehler im Induktionsargument?

Denkanstöße

- Prüfe beide unverzichtbaren Teile eines Induktionsbeweises getrennt. - Frage dich, ob die erste Aussage der Kette überhaupt wahr ist.

Lösung

1. Der Übergang von \(k\) auf \(k+1\) wäre formal korrekt, falls die Voraussetzung \(k=k+1\) wahr wäre. 2. Es gibt jedoch keinen gültigen Induktionsanfang: Bereits \(1=2\) ist falsch. 3. Ohne wahren Anfang kann der Induktionsschritt keine Aussageskette erzeugen.

Antwort

Der Induktionsanfang fehlt und ist sogar falsch. Deshalb beweist der korrekte Übergang allein nichts.

43794012

Beweise durch vollständige Induktion: \(1+3+5+\dots +(2n-1)=n^2\) für alle \(n\ge 1\).

Denkanstöße

- Vergleiche zwei aufeinanderfolgende Quadratzahlen. - Bestimme den Summanden, der beim nächsten Index hinzukommt.

Lösung

1. Für \(n=1\) gilt \(1=1^2\). 2. Es gelte \(1+3+\dots +(2k-1)=k^2\). 3. Durch Addition des nächsten ungeraden Summanden \(2k+1\) erhält man \(k^2+2k+1=(k+1)^2\). Damit gilt die Formel für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) gilt \(1+3+\dots +(2n-1)=n^2\).

43796612

Beweise durch vollständige Induktion, dass \(n^2+n\) für alle \(n\ge 0\) gerade ist.

Denkanstöße

- Schreibe den Ausdruck für den nächsten Index aus. - Trenne einen bereits bekannten Teil von einem offensichtlich geraden Rest.

Lösung

1. Für \(n=0\) ist \(0\) gerade. 2. Es sei \(k^2+k\) gerade. Dann gilt \((k+1)^2+(k+1)=k^2+k+2k+2\). 3. Beide Summanden sind gerade; daher ist auch der Ausdruck für \(k+1\) gerade.

Antwort

Für alle \(n\ge 0\) ist \(n^2+n\) gerade.

43800412

Die Folge ist durch \(a_1=1\) und \(a_{n+1}=3a_n\) definiert. Beweise \(a_n=3^{n-1}\).

Denkanstöße

- Prüfe den Exponenten beim ersten Folgenglied. - Die Rekursion multipliziert stets mit demselben Faktor.

Lösung

1. Für \(n=1\) gilt \(1=3^0\). 2. Es gelte \(a_k=3^{k-1}\). Dann ist \(a_{k+1}=3a_k=3^k\). 3. Dies ist die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(a_n=3^{n-1}\).

43801012

Die Folge ist durch \(a_1=-2\) und \(a_{n+1}=-a_n\) definiert. Beweise \(a_n=2(-1)^n\).

Denkanstöße

- Beobachte den regelmäßigen Vorzeichenwechsel. - Vergleiche ihn mit aufeinanderfolgenden Potenzen von \(-1\).

Lösung

1. Für \(n=1\) gilt \(-2=2(-1)^1\). 2. Es gelte \(a_k=2(-1)^k\). Dann ist \(a_{k+1}=-a_k=-2(-1)^k=2(-1)^{k+1}\). 3. Die Formel gilt für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) gilt \(a_n=2(-1)^n\).

43801412

Zu \(a_1=3\) und \(a_{n+1}=2a_n-1\) soll \(a_n=2^n+1\) bewiesen werden. Ein Schüler schreibt im Schritt nur: „Aus \(a_k=2^k+1\) folgt \(a_{k+1}=2^{k+1}+1\).“ Ergänze die fehlende Rechnung.

Denkanstöße

- Verwende zuerst die rekursive Definition und erst danach die Voraussetzung. - Jeder Gleichheitsschritt sollte eine erkennbare Begründung haben.

Lösung

1. Nach der Rekursion ist \(a_{k+1}=2a_k-1\). 2. Mit der Induktionsvoraussetzung folgt \(a_{k+1}=2(2^k+1)-1=2^{k+1}+1\). 3. Damit ist der Übergang begründet; der Anfang \(a_1=3=2^1+1\) stimmt ebenfalls.

Antwort

Die fehlende Rechnung lautet \(a_{k+1}=2a_k-1=2(2^k+1)-1=2^{k+1}+1\).

43801912

In einer Gruppe begrüßt jede Person jede andere Person genau einmal per Handschlag. Beweise, dass bei \(n\) Personen genau \(\frac{n(n-1)}{2}\) Handschläge stattfinden.

Denkanstöße

- Betrachte nur die zusätzlichen Begegnungen der neu hinzukommenden Person. - Alte Handschläge werden nicht verändert.

Lösung

1. Bei \(n=1\) gibt es \(0=\frac{1\cdot 0}{2}\) Handschläge. 2. Es gelte die Formel für \(k\) Personen. Eine neu hinzukommende Person gibt jeder der \(k\) bisherigen Personen genau einen Handschlag. 3. Daher steigt die Zahl auf \(\frac{k(k-1)}{2}+k=\frac{k(k+1)}{2}\), also auf die Formel für \(k+1\).

Antwort

Bei \(n\) Personen gibt es \(\frac{n(n-1)}{2}\) Handschläge.

43793012

Bestimme den kleinsten Startwert \(n_0\in\{0,1,2,3\}\), für den sich die Aussage \(2^n\ge n+1\) durch vollständige Induktion für alle \(n\ge n_0\) beweisen lässt. Führe den Beweis aus.

Denkanstöße

- Teste die vorgegebenen Startwerte der Reihe nach. - Untersuche, wie sich beide Seiten beim Übergang zum nächsten Index verändern.

Lösung

1. Für \(n=0\) gilt \(2^0=1=0+1\), also ist \(n_0=0\) möglich und minimal. 2. Aus \(2^k\ge k+1\) folgt \(2^{k+1}=2\cdot 2^k\ge 2k+2\ge k+2\) für \(k\ge 0\). 3. Damit gilt die Aussage für alle \(n\ge 0\).

Antwort

Der kleinste Startwert ist \(n_0=0\); für alle \(n\ge 0\) gilt \(2^n\ge n+1\).

43793112

Beweise durch vollständige Induktion, dass für alle \(n\ge 1\) gilt: \(\sum_{j=1}^{n}(3j-1)=\frac{n(3n+1)}{2}\).

Denkanstöße

- Betrachte beim nächsten Index nur den neu hinzukommenden Summanden. - Bringe die entstehende Summe auf eine gemeinsame Form.

Lösung

1. Für \(n=1\) gilt \(2=\frac{1\cdot 4}{2}\). 2. Es gelte \(\sum_{j=1}^{k}(3j-1)=\frac{k(3k+1)}{2}\). Dann ist \(\sum_{j=1}^{k+1}(3j-1)=\frac{k(3k+1)}{2}+3k+2=\frac{(k+1)(3k+4)}{2}\). Dies ist die Formel mit \(n=k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}(3j-1)=\frac{n(3n+1)}{2}\).

43793512

Beweise durch vollständige Induktion, dass \(7^n-1\) für alle \(n\ge 1\) durch \(6\) teilbar ist.

Denkanstöße

- Versuche, den Ausdruck mit dem nächsten Exponenten auf den vorherigen zurückzuführen. - Suche eine Zerlegung in bereits bekannte und offensichtlich passende Teile.

Lösung

1. Für \(n=1\) ist \(7^1-1=6\) durch \(6\) teilbar. 2. Es sei \(7^k-1\) durch \(6\) teilbar. Dann gilt \(7^{k+1}-1=7(7^k-1)+6\). 3. Beide Summanden sind durch \(6\) teilbar; daher gilt dies auch für \(7^{k+1}-1\).

Antwort

Für alle \(n\ge 1\) gilt \(6\mid (7^n-1)\).

43793612

Beweise für alle \(n\ge 0\): \(\sum_{j=0}^{n}(4j+1)=(n+1)(2n+1)\).

Denkanstöße

- Prüfe den besonderen Start bei \(0\). - Isoliere den neu hinzukommenden Summanden.

Lösung

1. Für \(n=0\) gilt \(1=(0+1)(2\cdot 0+1)\). 2. Es gelte \(\sum_{j=0}^{k}(4j+1)=(k+1)(2k+1)\). Dann kommt \(4(k+1)+1=4k+5\) hinzu. 3. Es folgt \((k+1)(2k+1)+4k+5=(k+2)(2k+3)\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 0\) ist \(\sum_{j=0}^{n}(4j+1)=(n+1)(2n+1)\).

43793812

Die Werte \(n^2+n+41\) sind für \(n=0,1,\dots,39\) Primzahlen. Erkläre, warum daraus keine allgemeine Aussage folgt, und widerlege die Behauptung „Für alle \(n\ge 0\) ist \(n^2+n+41\) prim“ mit einem passenden Wert.

Denkanstöße

- Suche einen Wert, bei dem sich der Ausdruck sichtbar faktorisieren lässt. - Ein einziges Gegenbeispiel genügt gegen eine Allaussage.

Lösung

1. Endlich viele überprüfte Werte ersetzen keinen Beweis für alle natürlichen Zahlen. 2. Für \(n=41\) ergibt sich \(41^2+41+41=41(41+2)=41\cdot 43\). 3. Dieser Wert ist zusammengesetzt; die allgemeine Behauptung ist daher falsch.

Antwort

Die Behauptung ist falsch, denn bei \(n=41\) erhält man \(41\cdot 43\), also keine Primzahl.

43794412

Beweise für alle \(n\ge 1\): \(\sum_{j=1}^{n}j(j+1)=\frac{n(n+1)(n+2)}{3}\).

Denkanstöße

- Klammere gemeinsame Faktoren aus, bevor du vollständig ausmultiplizierst. - Der neue Summand enthält bereits Teile der Zielgestalt.

Lösung

1. Für \(n=1\) gilt \(1\cdot 2=\frac{1\cdot 2\cdot 3}{3}\). 2. Es gelte die Formel für \(k\). Dann kommt \((k+1)(k+2)\) hinzu. 3. Es folgt \(\frac{k(k+1)(k+2)}{3}+(k+1)(k+2)=\frac{(k+1)(k+2)(k+3)}{3}\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}j(j+1)=\frac{n(n+1)(n+2)}{3}\).

43794812

Beweise für alle \(n\ge 1\): \(2+6+18+\dots +2\cdot 3^{n-1}=3^n-1\).

Denkanstöße

- Bestimme den nächsten Summanden über seinen Exponenten. - Fasse nach dem Einsetzen möglichst früh Potenzen gleicher Basis zusammen.

Lösung

1. Für \(n=1\) gilt \(2=3-1\). 2. Es gelte die Formel für \(k\). Dann ist die nächste Summe \(3^k-1+2\cdot 3^k=3\cdot 3^k-1=3^{k+1}-1\). 3. Damit gilt die Formel für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) ist \(2+6+\dots +2\cdot 3^{n-1}=3^n-1\).

43795112

Beweise für alle \(n\ge 1\): \(\prod_{j=1}^{n}\left(1+\frac{1}{j}\right)=n+1\).

Denkanstöße

- Forme den neu hinzukommenden Faktor als Bruch um. - Prüfe, welche Faktoren sich anschließend kürzen.

Lösung

1. Für \(n=1\) gilt \(1+\frac{1}{1}=2\). 2. Es gelte das Produkt bis \(k\) gleich \(k+1\). 3. Der neue Faktor ist \(1+\frac{1}{k+1}=\frac{k+2}{k+1}\). Daher wird das Produkt \((k+1)\frac{k+2}{k+1}=k+2\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\prod_{j=1}^{n}\left(1+\frac{1}{j}\right)=n+1\).

43796012

Beweise für alle \(n\ge 1\): \(\prod_{j=1}^{n}2^{2j-1}=2^{n^2}\).

Denkanstöße

- Beim Multiplizieren gleicher Basen werden die Exponenten zusammengeführt. - Vergleiche die Differenz zweier aufeinanderfolgender Quadrate.

Lösung

1. Für \(n=1\) gilt \(2^1=2^{1^2}\). 2. Es gelte das Produkt bis \(k\) gleich \(2^{k^2}\). 3. Multiplikation mit \(2^{2(k+1)-1}=2^{2k+1}\) ergibt \(2^{k^2+2k+1}=2^{(k+1)^2}\). Damit gilt die Formel für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) gilt \(\prod_{j=1}^{n}2^{2j-1}=2^{n^2}\).

43796712

Beweise für alle \(n\ge 0\), dass \(n^3-n\) durch \(6\) teilbar ist.

Denkanstöße

- Forme den neuen Ausdruck so um, dass der alte wieder erscheint. - Nutze eine elementare Eigenschaft zweier aufeinanderfolgender Zahlen.

Lösung

1. Für \(n=0\) ist der Ausdruck \(0\). 2. Es sei \(k^3-k\) durch \(6\) teilbar. Dann ist \((k+1)^3-(k+1)=(k^3-k)+3k(k+1)\). 3. Das Produkt \(k(k+1)\) ist gerade, daher ist \(3k(k+1)\) durch \(6\) teilbar. Somit gilt die Behauptung für \(k+1\).

Antwort

Für alle \(n\ge 0\) gilt \(6\mid(n^3-n)\).

43796912

Beweise für alle \(n\ge 0\), dass \(2^{3n}-1\) durch \(7\) teilbar ist.

Denkanstöße

- Beachte, um welchen Faktor die Potenz beim nächsten Index wächst. - Suche eine Zerlegung mit einem konstanten Restterm.

Lösung

1. Für \(n=0\) ist der Ausdruck \(0\). 2. Es sei \(2^{3k}-1\) durch \(7\) teilbar. Dann gilt \(2^{3(k+1)}-1=8\cdot 2^{3k}-1=8(2^{3k}-1)+7\). 3. Beide Summanden sind durch \(7\) teilbar.

Antwort

Für alle \(n\ge 0\) gilt \(7\mid(2^{3n}-1)\).

43797112

Beweise für alle \(n\ge 0\), dass \(4^n+2\) durch \(3\) teilbar ist.

Denkanstöße

- Versuche, den neuen Ausdruck als Vielfaches des alten plus einen Rest zu schreiben. - Prüfe, ob der Rest dieselbe Teilbarkeit besitzt.

Lösung

1. Für \(n=0\) gilt \(4^0+2=3\). 2. Es sei \(4^k+2\) durch \(3\) teilbar. Dann ist \(4^{k+1}+2=4(4^k+2)-6\). 3. Beide Terme sind durch \(3\) teilbar; daher gilt die Behauptung für \(k+1\).

Antwort

Für alle \(n\ge 0\) gilt \(3\mid(4^n+2)\).

43797812

Beweise für alle \(n\ge 0\), dass \(2n^3+3n^2+n\) durch \(6\) teilbar ist.

Denkanstöße

- Berechne nicht den ganzen neuen Ausdruck isoliert, sondern seine Differenz zum alten. - Suche dabei nach einem gemeinsamen Faktor aller neuen Terme.

Lösung

1. Für \(n=0\) ist der Ausdruck \(0\). 2. Es sei der Ausdruck für \(k\) durch \(6\) teilbar. Die Differenz zum Wert bei \(k+1\) ist \(6(k+1)^2\). 3. Diese Differenz ist durch \(6\) teilbar; daher gilt die Behauptung für \(k+1\).

Antwort

Für alle \(n\ge 0\) gilt \(6\mid(2n^3+3n^2+n)\).

43797912

Bestimme \(c\in\{0,1,2,3\}\) so, dass \(5^n+c\) für alle \(n\ge 0\) durch \(4\) teilbar ist. Beweise die gefundene Aussage durch vollständige Induktion.

Denkanstöße

- Der erste zulässige Index schränkt den unbekannten Wert bereits stark ein. - Führe danach den neuen Ausdruck auf den alten zurück.

Lösung

1. Für \(n=0\) muss \(1+c\) durch \(4\) teilbar sein; daraus folgt in der vorgegebenen Menge \(c=3\). 2. Für \(n=0\) gilt \(5^0+3=4\). 3. Aus der Teilbarkeit von \(5^k+3\) folgt \(5^{k+1}+3=5(5^k+3)-12\), also wiederum Teilbarkeit durch \(4\).

Antwort

Es ist \(c=3\). Dann gilt \(4\mid(5^n+3)\) für alle \(n\ge 0\).

43798012

Sei \(a\ge 2\) eine ganze Zahl. Beweise für alle \(n\ge 1\), dass \(a^n-1\) durch \(a-1\) teilbar ist.

Denkanstöße

- Behandle \(a\) als festen Parameter und induziere nur über den Exponenten. - Suche eine Zerlegung, in der der vorherige Exponent vorkommt.

Lösung

1. Für \(n=1\) ist \(a-1\) durch \(a-1\) teilbar. 2. Es sei \(a^k-1\) durch \(a-1\) teilbar. Dann gilt \(a^{k+1}-1=a(a^k-1)+(a-1)\). 3. Beide Summanden sind durch \(a-1\) teilbar.

Antwort

Für jede ganze Zahl \(a\ge 2\) und alle \(n\ge 1\) gilt \((a-1)\mid(a^n-1)\).

43798712

Beweise für alle \(n\ge 0\): \(3^n\ge 2n+1\).

Denkanstöße

- Vergleiche nach dem Multiplizieren nur noch zwei lineare Ausdrücke. - Achte auf den Startwert \(0\).

Lösung

1. Für \(n=0\) gilt \(1=1\). 2. Es gelte \(3^k\ge 2k+1\). Dann ist \(3^{k+1}\ge 6k+3\). 3. Wegen \(6k+3\ge 2k+3\) für \(k\ge 0\) folgt \(3^{k+1}\ge 2(k+1)+1\).

Antwort

Für alle \(n\ge 0\) gilt \(3^n\ge 2n+1\).

43798812

Beweise für alle \(n\ge 1\): \(n!\ge 2^{n-1}\).

Denkanstöße

- Nutze die Beziehung zwischen zwei aufeinanderfolgenden Fakultäten. - Nach Einsetzen der Voraussetzung genügt eine einfache Abschätzung eines Faktors.

Lösung

1. Für \(n=1\) gilt \(1!=1=2^0\). 2. Es gelte \(k!\ge 2^{k-1}\). Dann ist \((k+1)!=(k+1)k!\ge (k+1)2^{k-1}\). 3. Für \(k\ge 1\) gilt \(k+1\ge 2\), also \((k+1)!\ge 2^k\).

Antwort

Für alle \(n\ge 1\) gilt \(n!\ge 2^{n-1}\).

43798912

Beweise für alle \(n\ge 4\): \(n!>2^n\).

Denkanstöße

- Prüfe den angegebenen Startwert genau. - Vergleiche im Schritt nur den neu hinzukommenden Faktor mit dem Wachstumsfaktor der rechten Seite.

Lösung

1. Für \(n=4\) gilt \(24>16\). 2. Es gelte \(k!>2^k\) für ein \(k\ge 4\). Dann ist \((k+1)!=(k+1)k!>(k+1)2^k\). 3. Da \(k+1>2\), folgt \((k+1)!>2^{k+1}\).

Antwort

Für alle \(n\ge 4\) gilt \(n!>2^n\).

43799012

Beweise für alle \(n\ge 1\): \(1+\frac12+\frac13+\dots +\frac1n\le \frac{n+1}{2}\).

Denkanstöße

- Untersuche nur, wie groß der neue Summand höchstens ist. - Vergleiche die Zunahme der rechten Seite mit diesem neuen Summanden.

Lösung

1. Für \(n=1\) gilt \(1=1\). 2. Es gelte die Ungleichung für \(k\). Dann ist die nächste Summe höchstens \(\frac{k+1}{2}+\frac{1}{k+1}\). 3. Für \(k\ge 1\) gilt \(\frac{1}{k+1}\le \frac12\), daher ist die Summe höchstens \(\frac{k+2}{2}\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}\frac1j\le \frac{n+1}{2}\).

43799812

Beweise für alle \(n\ge 0\): \(1+\frac12+\frac1{2^2}+\dots +\frac1{2^n}<2\).

Denkanstöße

- Eine genaue Formel kann leichter zu beweisen sein als nur die Abschätzung. - Vergleiche die Restterme bei zwei aufeinanderfolgenden Indizes.

Lösung

1. Für \(n=0\) gilt \(1=2-\frac{1}{2^0}<2\). 2. Es gelte \(1+\frac12+\dots +\frac{1}{2^k}=2-\frac{1}{2^k}\). 3. Beim Übergang wird \(\frac{1}{2^{k+1}}\) addiert, sodass \(2-\frac{1}{2^k}+\frac{1}{2^{k+1}}=2-\frac{1}{2^{k+1}}<2\) entsteht.

Antwort

Für alle \(n\ge 0\) ist \(1+\frac12+\dots +\frac1{2^n}=2-\frac1{2^n}<2\).

43800112

Die Folge ist durch \(a_1=3\) und \(a_{n+1}=2a_n+1\) definiert. Beweise \(a_n=2^{n+1}-1\).

Denkanstöße

- Setze die vermutete Formel direkt in die Rekursion ein. - Achte auf den um eins verschobenen Exponenten.

Lösung

1. Für \(n=1\) gilt \(3=2^2-1\). 2. Es gelte \(a_k=2^{k+1}-1\). Dann ist \(a_{k+1}=2(2^{k+1}-1)+1=2^{k+2}-1\). 3. Dies ist die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(a_n=2^{n+1}-1\).

43801112

Die Folge ist durch \(a_1=1\) und \(a_{n+1}=\frac{a_n+2}{2}\) definiert. Beweise für alle \(n\ge 1\): \(1\le a_n<2\).

Denkanstöße

- Übertrage die untere und obere Schranke getrennt durch die Rekursion. - Beachte, dass die Rekursion auf beiden Seiten monoton ist.

Lösung

1. Für \(n=1\) gilt \(1\le a_1<2\). 2. Es gelte \(1\le a_k<2\). Dann ist \(a_{k+1}=\frac{a_k+2}{2}\ge \frac{3}{2}\ge 1\). 3. Aus \(a_k<2\) folgt \(a_{k+1}<\frac{4}{2}=2\). Damit bleibt das Intervall erhalten.

Antwort

Für alle \(n\ge 1\) gilt \(1\le a_n<2\).

43801312

Eine Folge von Summen ist rekursiv durch \(S_1=2\) und \(S_{n+1}=S_n+3n+2\) gegeben. Beweise \(S_n=\frac{3n^2+n}{2}\).

Denkanstöße

- Setze die vermutete Formel in die Rekursion ein. - Vergleiche den entstehenden Zähler mit der Zielseite für den nächsten Index.

Lösung

1. Für \(n=1\) gilt \(S_1=2=\frac{3+1}{2}\). 2. Es gelte \(S_k=\frac{3k^2+k}{2}\). Dann ist \(S_{k+1}=\frac{3k^2+k}{2}+3k+2\). 3. Zusammenfassen ergibt \(\frac{3k^2+7k+4}{2}=\frac{3(k+1)^2+(k+1)}{2}\).

Antwort

Für alle \(n\ge 1\) gilt \(S_n=\frac{3n^2+n}{2}\).

43801612

Beweise durch vollständige Induktion, dass die Innenwinkelsumme eines konvexen \(n\)-Ecks für \(n\ge 3\) gleich \((n-2)\cdot 180^{\circ}\) ist.

Denkanstöße

- Zerlege das größere Vieleck in ein kleineres Vieleck und eine einfache Grundfigur. - Untersuche, um wie viel die Winkelsumme bei einem neuen Eckpunkt wächst.

Lösung

1. Für ein Dreieck gilt die Innenwinkelsumme \(180^{\circ}=(3-2)\cdot 180^{\circ}\). 2. Füge einem konvexen \(k\)-Eck einen neuen Eckpunkt so hinzu, dass ein \((k+1)\)-Eck entsteht. Eine Diagonale zerlegt das neue Vieleck in das alte \(k\)-Eck und ein Dreieck. 3. Die Winkelsumme wächst daher um \(180^{\circ}\) auf \((k-2)\cdot 180^{\circ}+180^{\circ}=(k-1)\cdot 180^{\circ}\).

Antwort

Die Innenwinkelsumme beträgt \((n-2)\cdot 180^{\circ}\).

43801812

Beweise durch vollständige Induktion: Eine Menge mit \(n\) Elementen besitzt genau \(2^n\) Teilmengen.

Denkanstöße

- Ordne die neuen Teilmengen danach, ob sie das neue Element enthalten. - Stelle eine eindeutige Zuordnung zu den alten Teilmengen her.

Lösung

1. Die leere Menge besitzt genau eine Teilmenge, also \(2^0\). 2. Es sei die Aussage für eine \(k\)-elementige Menge wahr. Füge ein neues Element hinzu. 3. Zu jeder alten Teilmenge gibt es genau zwei Teilmengen der neuen Menge: eine ohne und eine mit dem neuen Element. Daher verdoppelt sich die Anzahl von \(2^k\) auf \(2^{k+1}\).

Antwort

Eine \(n\)-elementige Menge besitzt genau \(2^n\) Teilmengen.

43802012

Aus \(n\) gleich großen Quadraten wird eine lückenlose gerade Reihe gelegt, wobei benachbarte Quadrate jeweils eine ganze Seite gemeinsam haben. Beweise, dass der Rand der Figur aus \(2n+2\) Quadratseiten besteht.

Denkanstöße

- Zähle beim Anfügen nur verschwundene und neu sichtbare Seiten. - Unterscheide Bruttozuwachs und Nettozuwachs.

Lösung

1. Für \(n=1\) besteht der Rand aus \(4=2\cdot 1+2\) Seiten. 2. Es gelte die Formel für \(k\) Quadrate. Beim Anfügen eines weiteren Quadrats verschwindet eine bisherige Randseite im Inneren, während drei neue Randseiten hinzukommen. 3. Die Randzahl wächst netto um \(2\) auf \(2k+2+2=2(k+1)+2\).

Antwort

Der Rand besteht bei \(n\) Quadraten aus \(2n+2\) Quadratseiten.

43802112

Für \(f(x)=e^{2x}\) beweise durch vollständige Induktion über \(n\ge 0\): \(f^{(n)}(x)=2^n e^{2x}\).

Denkanstöße

- Prüfe, wie sich der konstante Faktor bei jeder weiteren Ableitung verändert. - Behandle den Funktionswert selbst als Ableitung der Ordnung \(0\).

Lösung

1. Für \(n=0\) gilt \(f^{(0)}(x)=f(x)=e^{2x}=2^0e^{2x}\). 2. Es gelte \(f^{(k)}(x)=2^ke^{2x}\). 3. Ableiten ergibt \(f^{(k+1)}(x)=2^k\cdot 2e^{2x}=2^{k+1}e^{2x}\).

Antwort

Für alle \(n\ge 0\) gilt \(f^{(n)}(x)=2^ne^{2x}\).

43802512

Im Induktionsschritt für \(\sum_{j=1}^{n}\frac{1}{j(j+1)}=\frac{n}{n+1}\) fehlt der letzte Term: \(\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\boxed{\;\;\;\;\;}\). Bestimme den fehlenden Ausdruck und erkläre, warum damit der Induktionsschritt abgeschlossen ist.

Denkanstöße

- Bringe beide Brüche auf einen gemeinsamen Nenner. - Vergleiche das Ergebnis mit der Zielaussage beim nächsten Index.

Lösung

1. Auf gemeinsamen Nenner gebracht ergibt sich \(\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{(k+1)^2}{(k+1)(k+2)}=\frac{k+1}{k+2}\). 2. Dieser Ausdruck ist genau die behauptete rechte Seite für \(n=k+1\). Damit ist der Induktionsschritt vollständig.

Antwort

Der fehlende Ausdruck ist \(\frac{k+1}{k+2}\).

43794612

Beweise durch vollständige Induktion die Quadratsummenformel \(1^2+2^2+\dots +n^2=\frac{n(n+1)(2n+1)}{6}\) für alle \(n\ge 1\).

Denkanstöße

- Ziehe im Induktionsschritt einen gemeinsamen Faktor heraus. - Vergleiche die verbleibenden Faktoren mit der Zielgestalt.

Lösung

1. Für \(n=1\) stimmen beide Seiten mit \(1\) überein. 2. Es gelte die Formel für \(k\). Nach Addition von \((k+1)^2\) erhält man \(\frac{k(k+1)(2k+1)}{6}+(k+1)^2\). 3. Ausklammern und Zusammenfassen ergibt \(\frac{(k+1)(k+2)(2k+3)}{6}\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}j^2=\frac{n(n+1)(2n+1)}{6}\).

43794712

Beweise für alle \(n\ge 1\): \(1-2+3-4+\dots +(-1)^{n+1}n=\frac{1+(-1)^{n+1}(2n+1)}{4}\).

Denkanstöße

- Behalte das wechselnde Vorzeichen beim nächsten Index sorgfältig im Blick. - Ersetze zwei aufeinanderfolgende Potenzen von \(-1\) passend.

Lösung

1. Für \(n=1\) liefern beide Seiten \(1\). 2. Es gelte die Formel für \(k\). Zum nächsten Index kommt \((-1)^{k+2}(k+1)\) hinzu. 3. Mit \((-1)^{k+1}=-(-1)^{k+2}\) wird die Summe zu \(\frac{1+(-1)^{k+2}(2k+3)}{4}\), also zur Formel für \(k+1\).

Antwort

Die angegebene Formel gilt für alle \(n\ge 1\).

43794912

Beweise durch vollständige Induktion: \(\sum_{j=1}^{n}j\cdot 2^{j-1}=(n-1)\cdot 2^n+1\) für alle \(n\ge 1\).

Denkanstöße

- Achte darauf, dass der neue Summand denselben Potenzfaktor wie ein Teil der Voraussetzung besitzt. - Vergleiche den Koeffizienten vor der Potenz mit dem Zielindex.

Lösung

1. Für \(n=1\) gilt \(1=0\cdot 2+1\). 2. Es gelte die Formel für \(k\). Dann kommt \((k+1)\cdot 2^k\) hinzu. 3. Es folgt \((k-1)\cdot 2^k+1+(k+1)\cdot 2^k=2k\cdot 2^k+1=k\cdot 2^{k+1}+1\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}j\cdot 2^{j-1}=(n-1)\cdot 2^n+1\).

43795212

Beweise für alle \(n\ge 2\): \(\prod_{j=2}^{n}\left(1-\frac{1}{j^2}\right)=\frac{n+1}{2n}\).

Denkanstöße

- Zerlege die Differenz im neuen Faktor in ein Produkt. - Kürze systematisch, bevor du das Ergebnis vergleichst.

Lösung

1. Für \(n=2\) gilt \(1-\frac{1}{4}=\frac{3}{4}=\frac{2+1}{2\cdot 2}\). 2. Es gelte die Formel für \(k\). Der nächste Faktor ist \(1-\frac{1}{(k+1)^2}=\frac{k(k+2)}{(k+1)^2}\). 3. Das Produkt wird \(\frac{k+1}{2k}\cdot\frac{k(k+2)}{(k+1)^2}=\frac{k+2}{2(k+1)}\), also die Zielgestalt für \(k+1\).

Antwort

Für alle \(n\ge 2\) gilt \(\prod_{j=2}^{n}\left(1-\frac{1}{j^2}\right)=\frac{n+1}{2n}\).

43795312

Beweise durch vollständige Induktion: \(1^3+2^3+\dots +n^3=\left(\frac{n(n+1)}{2}\right)^2\) für alle \(n\ge 1\).

Denkanstöße

- Klammere eine möglichst große gemeinsame Potenz aus. - Vergleiche den verbleibenden Ausdruck mit einem vollständigen Quadrat.

Lösung

1. Für \(n=1\) gilt \(1=1\). 2. Es gelte die Formel für \(k\). Nach Addition von \((k+1)^3\) erhält man \(\frac{k^2(k+1)^2}{4}+(k+1)^3\). 3. Ausklammern liefert \(\frac{(k+1)^2(k+2)^2}{4}=\left(\frac{(k+1)(k+2)}{2}\right)^2\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}j^3=\left(\frac{n(n+1)}{2}\right)^2\).

43795512

Beweise für alle \(n\ge 1\): \(\sum_{j=1}^{n}\frac{1}{j(j+3)}=\frac13\left(1+\frac12+\frac13-\frac{1}{n+1}-\frac{1}{n+2}-\frac{1}{n+3}\right)\).

Denkanstöße

- Suche eine Darstellung des neuen Summanden als Differenz zweier Brüche. - Beobachte, welche Randterme beim nächsten Index verschwinden oder neu erscheinen.

Lösung

1. Für \(n=1\) ist die rechte Seite \(\frac13\left(1-\frac14\right)=\frac14\), also gleich der linken Seite. 2. Es gelte die Formel für \(k\). Addiert wird \(\frac{1}{(k+1)(k+4)}=\frac13\left(\frac{1}{k+1}-\frac{1}{k+4}\right)\). 3. Der Term \(-\frac{1}{k+1}\) fällt weg; übrig bleibt genau die rechte Seite mit \(n=k+1\).

Antwort

Die angegebene Formel gilt für alle \(n\ge 1\).

43795812

Beweise für alle \(n\ge 1\): \(\sum_{j=1}^{n}\frac{j}{2^j}=2-\frac{n+2}{2^n}\).

Denkanstöße

- Bringe die beiden letzten Brüche auf dieselbe Zweierpotenz. - Vergleiche den neuen Zähler mit dem nächsten Index.

Lösung

1. Für \(n=1\) gilt \(\frac12=2-\frac32\). 2. Es gelte die Formel für \(k\). Dann ist die nächste Summe \(2-\frac{k+2}{2^k}+\frac{k+1}{2^{k+1}}\). 3. Auf den Nenner \(2^{k+1}\) gebracht ergibt sich \(2-\frac{k+3}{2^{k+1}}\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}\frac{j}{2^j}=2-\frac{n+2}{2^n}\).

43795912

Beweise für alle \(n\ge 1\): \(\sum_{j=1}^{n}j\cdot j!=(n+1)!-1\).

Denkanstöße

- Suche im neuen Summanden einen gemeinsamen Fakultätsfaktor. - Nutze die Beziehung zwischen zwei aufeinanderfolgenden Fakultäten.

Lösung

1. Für \(n=1\) gilt \(1\cdot 1!=2!-1\). 2. Es gelte die Formel für \(k\). Dann ist die neue Summe \((k+1)!-1+(k+1)(k+1)!\). 3. Ausklammern ergibt \((k+2)(k+1)!-1=(k+2)!-1\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}j\cdot j!=(n+1)!-1\).

43797512

Beweise für alle \(n\ge 0\), dass \(11^n-(-1)^n\) durch \(12\) teilbar ist.

Denkanstöße

- Berücksichtige beim nächsten Index sowohl die Potenz von \(11\) als auch den Vorzeichenwechsel. - Suche eine Zerlegung in den alten Ausdruck und einen Rest.

Lösung

1. Für \(n=0\) ist der Ausdruck \(0\). 2. Es sei \(11^k-(-1)^k\) durch \(12\) teilbar. Dann ist \(11^{k+1}-(-1)^{k+1}=11(11^k-(-1)^k)+12(-1)^k\). 3. Beide Summanden sind durch \(12\) teilbar.

Antwort

Für alle \(n\ge 0\) gilt \(12\mid\left(11^n-(-1)^n\right)\).

43797612

Beweise für alle \(n\ge 0\), dass \(n^5-n\) durch \(5\) teilbar ist.

Denkanstöße

- Vergleiche den Ausdruck für zwei aufeinanderfolgende Indizes. - Prüfe, ob alle neu auftretenden Koeffizienten einen gemeinsamen Teiler besitzen.

Lösung

1. Für \(n=0\) ist der Ausdruck \(0\). 2. Es sei \(k^5-k\) durch \(5\) teilbar. Die Differenz zum nächsten Ausdruck ist \((k+1)^5-(k+1)-(k^5-k)=5k^4+10k^3+10k^2+5k\). 3. Diese Differenz ist ein Vielfaches von \(5\); daher gilt die Teilbarkeit auch für \(k+1\).

Antwort

Für alle \(n\ge 0\) gilt \(5\mid(n^5-n)\).

43798412

Die Aussage „\(2^n+1\) ist für alle \(n\ge 0\) durch \(3\) teilbar“ ist falsch. Formuliere eine korrekte Aussage für alle ungeraden Exponenten und beweise sie durch Induktion über \(m\).

Denkanstöße

- Ersetze einen ungeraden Exponenten durch eine passende allgemeine Form. - Beachte, um welchen Faktor die Potenz beim nächsten Wert des neuen Index wächst.

Lösung

1. Korrekt ist: \(2^{2m+1}+1\) ist für alle \(m\ge 0\) durch \(3\) teilbar. Für \(m=0\) gilt \(2^1+1=3\). 2. Es sei \(2^{2k+1}+1\) durch \(3\) teilbar. 3. Dann ist \(2^{2(k+1)+1}+1=4\cdot 2^{2k+1}+1=4(2^{2k+1}+1)-3\), also durch \(3\) teilbar.

Antwort

Für alle \(m\ge 0\) gilt \(3\mid(2^{2m+1}+1)\).

43798612

Die Behauptung \(2^n\ge n^2\) ist nicht für alle \(n\ge 1\) wahr. Finde das kleinste Gegenbeispiel, bestimme den kleinsten geeigneten neuen Startwert und beweise die korrigierte Aussage durch vollständige Induktion.

Denkanstöße

- Prüfe zuerst kleine Werte systematisch. - Der Startwert muss sowohl die Aussage als auch die Abschätzung im Schritt tragen.

Lösung

1. Für \(n=3\) gilt \(8<9\); damit ist \(n=3\) das kleinste Gegenbeispiel. Der kleinste geeignete neue Startwert ist \(n_0=4\). 2. Für \(n=4\) gilt \(16=16\). 3. Aus \(2^k\ge k^2\) folgt \(2^{k+1}\ge 2k^2\). Für \(k\ge 4\) gilt \(2k^2\ge (k+1)^2\), denn \(k^2-2k-1=(k-1)^2-2\ge 7\). Somit gilt \(2^n\ge n^2\) für alle \(n\ge 4\).

Antwort

Das kleinste Gegenbeispiel ist \(n=3\). Der kleinste geeignete neue Startwert ist \(n_0=4\); für alle \(n\ge 4\) gilt \(2^n\ge n^2\).

43799212

Beweise für alle \(n\ge 2\): \(1^2+2^2+\dots +n^2<n^3\).

Denkanstöße

- Vergleiche den neuen Summanden mit der Differenz der beiden rechten Seiten. - Vereinfache die verbleibende Polynomungleichung.

Lösung

1. Für \(n=2\) gilt \(1+4=5<8\). 2. Es gelte die Ungleichung für \(k\ge 2\). Dann ist die nächste Summe kleiner als \(k^3+(k+1)^2\). 3. Es gilt \((k+1)^3-k^3=3k^2+3k+1>(k+1)^2\) für \(k\ge 1\). Daher ist \(k^3+(k+1)^2<(k+1)^3\).

Antwort

Für alle \(n\ge 2\) gilt \(\sum_{j=1}^{n}j^2<n^3\).

43799412

Beweise für alle \(n\ge 2\): \(4^n\ge n^3\).

Denkanstöße

- Vergleiche im Schritt den Faktor \(4\) mit dem Verhältnis benachbarter Kuben. - Prüfe die verbleibende Ungleichung am kleinsten zulässigen Index.

Lösung

1. Für \(n=2\) gilt \(16\ge 8\). 2. Es gelte \(4^k\ge k^3\) für \(k\ge 2\). Dann ist \(4^{k+1}\ge 4k^3\). 3. Für \(k\ge 2\) gilt \(4k^3\ge (k+1)^3\), denn \(4k^3-(k+1)^3=(k-2)(3k^2+3k+3)+5>0\). Somit folgt die Behauptung.

Antwort

Für alle \(n\ge 2\) gilt \(4^n\ge n^3\).

43799512

Beweise für alle \(n\ge 3\): \(1+2+\dots +n<2^n\).

Denkanstöße

- Vergleiche den neuen Summanden mit der bisherigen rechten Seite. - Eine bereits bekannte einfache Exponentialabschätzung kann den letzten Schritt tragen.

Lösung

1. Für \(n=3\) gelten \(1+2+3=6<8=2^3\) und die Hilfsungleichung \(4\le 8\). 2. Es gelte für ein \(k\ge 3\), dass \(1+2+\dots +k<2^k\) und \(k+1\le 2^k\). Dann ist \(1+2+\dots +(k+1)<2^k+k+1\le 2^{k+1}\). 3. Außerdem gilt \(k+2\le 2(k+1)\le 2^{k+1}\). Damit sind sowohl die Behauptung als auch die Hilfsungleichung für \(k+1\) gezeigt.

Antwort

Für alle \(n\ge 3\) gilt \(1+2+\dots +n<2^n\).

43799712

Beweise für alle \(n\ge 3\): \(3^n>n^2\).

Denkanstöße

- Nach Anwendung der Voraussetzung bleibt ein Vergleich zweier Quadratausdrücke. - Prüfe, ab welchem Index dieser Vergleich streng gilt.

Lösung

1. Für \(n=3\) gilt \(27>9\). 2. Es gelte \(3^k>k^2\). Dann ist \(3^{k+1}>3k^2\). 3. Für \(k\ge 2\) gilt \(3k^2>(k+1)^2\), denn \(2k^2-2k-1=2k(k-1)-1>0\). Somit gilt die Aussage für \(k+1\).

Antwort

Für alle \(n\ge 3\) gilt \(3^n>n^2\).

43800512

Die Folge ist durch \(a_1=2\) und \(a_{n+1}=2-\frac{1}{a_n}\) definiert. Beweise \(a_n=\frac{n+1}{n}\) für alle \(n\ge 1\).

Denkanstöße

- Setze die vermutete Bruchform in die Rekursion ein. - Vereinfache den Kehrwert sorgfältig.

Lösung

1. Für \(n=1\) gilt \(2=\frac21\). 2. Es gelte \(a_k=\frac{k+1}{k}\). Dann ist \(a_{k+1}=2-\frac{k}{k+1}=\frac{k+2}{k+1}\). 3. Dies ist die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(a_n=\frac{n+1}{n}\).

43800612

Die Folge ist durch \(a_1=\frac12\) und \(a_{n+1}=\frac{a_n}{1+a_n}\) definiert. Beweise \(a_n=\frac{1}{n+1}\).

Denkanstöße

- Setze die vermutete Formel vollständig in Zähler und Nenner ein. - Vereinfache den Doppelbruch schrittweise.

Lösung

1. Für \(n=1\) gilt \(a_1=\frac12\). 2. Es gelte \(a_k=\frac{1}{k+1}\). Dann ist \(a_{k+1}=\frac{\frac{1}{k+1}}{1+\frac{1}{k+1}}=\frac{1}{k+2}\). 3. Somit gilt die Formel für alle \(n\ge 1\).

Antwort

Für alle \(n\ge 1\) gilt \(a_n=\frac{1}{n+1}\).

43800712

Für die Fibonacci-Folge \(F_1=1\), \(F_2=1\), \(F_{n+2}=F_{n+1}+F_n\) beweise \(\sum_{j=1}^{n}F_j=F_{n+2}-1\) für alle \(n\ge 1\).

Denkanstöße

- Der neue Summand lässt sich mit dem bisherigen Randterm über die Rekursion verbinden. - Achte auf die Indexverschiebung in der Zielseite.

Lösung

1. Für \(n=1\) gilt \(F_1=1=F_3-1\). 2. Es gelte \(\sum_{j=1}^{k}F_j=F_{k+2}-1\). 3. Nach Addition von \(F_{k+1}\) entsteht \(F_{k+2}+F_{k+1}-1=F_{k+3}-1\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}F_j=F_{n+2}-1\).

43800812

Für die Fibonacci-Folge \(F_1=1\), \(F_2=1\), \(F_{n+2}=F_{n+1}+F_n\) beweise \(\sum_{j=1}^{n}F_j^2=F_nF_{n+1}\) für alle \(n\ge 1\).

Denkanstöße

- Klammere den gemeinsamen Fibonacci-Faktor aus. - Verwende danach die rekursive Definition genau einmal.

Lösung

1. Für \(n=1\) gilt \(F_1^2=1=F_1F_2\). 2. Es gelte \(\sum_{j=1}^{k}F_j^2=F_kF_{k+1}\). 3. Nach Addition von \(F_{k+1}^2\) erhält man \(F_{k+1}(F_k+F_{k+1})=F_{k+1}F_{k+2}\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}F_j^2=F_nF_{n+1}\).

43801212

Die Folge ist durch \(a_1=1\) und \(a_{n+1}=\sqrt{2+a_n}\) definiert. Beweise für alle \(n\ge 1\): \(1\le a_n<2\).

Denkanstöße

- Überprüfe beide Intervallgrenzen getrennt. - Nutze, dass die Wurzelfunktion für nichtnegative Argumente wächst.

Lösung

1. Für \(n=1\) gilt \(1\le a_1<2\). 2. Es gelte \(1\le a_k<2\). Dann ist \(a_{k+1}=\sqrt{2+a_k}\ge \sqrt3>1\). 3. Aus \(a_k<2\) folgt \(2+a_k<4\) und damit \(a_{k+1}<2\). Somit gilt die Schranke für alle \(n\).

Antwort

Für alle \(n\ge 1\) gilt \(1\le a_n<2\).

43802212

Für \(f(x)=xe^x\) beweise durch vollständige Induktion: \(f^{(n)}(x)=(x+n)e^x\) für alle \(n\ge 0\).

Denkanstöße

- Beim Ableiten entstehen zwei Beiträge, die denselben Exponentialfaktor besitzen. - Vergleiche den linearen Faktor vor und nach dem Ableiten.

Lösung

1. Für \(n=0\) gilt \(f(x)=(x+0)e^x\). 2. Es gelte \(f^{(k)}(x)=(x+k)e^x\). 3. Mit der Produktregel folgt \(f^{(k+1)}(x)=e^x+(x+k)e^x=(x+k+1)e^x\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 0\) gilt \(f^{(n)}(x)=(x+n)e^x\).

43802412

Beim Turm-von-Hanoi-Spiel sollen \(n\) verschieden große Scheiben von einem Stab auf einen anderen bewegt werden. Pro Zug darf nur eine Scheibe bewegt werden, und nie darf eine größere auf einer kleineren liegen. Beweise, dass mindestens \(2^n-1\) Züge nötig sind und dass diese Zahl erreichbar ist.

Denkanstöße

- Konzentriere dich auf den unvermeidlichen Zug der größten Scheibe. - Zerlege den gesamten Ablauf in die Phasen davor, diesen Zug und die Phase danach. - Für Untertürme gilt dieselbe Art von Aufgabe.

Lösung

1. Für \(n=1\) genügt und erfordert das Spiel \(1=2^1-1\) Zug. 2. Für \(k+1\) Scheiben müssen zunächst die oberen \(k\) Scheiben auf den Hilfsstab gelangen, dann die größte Scheibe bewegt und anschließend die \(k\) Scheiben auf sie gelegt werden. Nach Induktionsvoraussetzung sind dafür mindestens \((2^k-1)+1+(2^k-1)=2^{k+1}-1\) Züge nötig. 3. Werden beide Teilaufgaben jeweils optimal ausgeführt, wird diese Zahl tatsächlich erreicht.

Antwort

Die minimale Zugzahl beträgt für \(n\) Scheiben genau \(2^n-1\).

43794512

Verschiedene Geraden zerlegen die Ebene in Gebiete. Beweise durch vollständige Induktion über die Anzahl der Geraden: Die Gebiete lassen sich stets mit zwei Farben so färben, dass Gebiete mit einem gemeinsamen Randstück verschiedene Farben haben.

Denkanstöße

- Überlege, was sich beim Hinzufügen genau einer neuen Geraden ändert. - Suche eine einheitliche Änderung auf einer ganzen Seite der neuen Geraden. - Prüfe alte und neue Nachbarschaften getrennt.

Lösung

1. Bei \(0\) Geraden gibt es nur ein Gebiet; eine Färbung ist möglich. 2. Es sei eine passende Färbung für \(k\) verschiedene Geraden gegeben. Füge eine weitere, von den bisherigen verschiedene Gerade hinzu. 3. Auf einer Seite der neuen Geraden bleiben alle Farben unverändert, auf der anderen Seite werden alle Farben vertauscht. Alte Nachbarschaften bleiben verschieden gefärbt. Zwei Gebiete beiderseits der neuen Geraden gehörten zuvor zum selben Gebiet und erhalten nach dem Farbtausch verschiedene Farben. Damit gilt die Aussage für \(k+1\) Geraden.

Antwort

Die Zweifärbung ist für jede endliche Anzahl von Geraden möglich; der Induktionsschritt gelingt durch Farbtausch in einer der beiden Halbebenen.

43796112

Beweise mit vollständiger Induktion und der Pascalschen Formel, dass \(\sum_{j=0}^{n}\binom{n}{j}=2^n\) für alle \(n\ge 0\) gilt.

Denkanstöße

- Schreibe jeden Eintrag der nächsten Zeile als Summe zweier Einträge der vorherigen Zeile. - Achte bei den Randwerten auf die passenden Summengrenzen.

Lösung

1. Für \(n=0\) gilt \(\binom{0}{0}=1=2^0\). 2. Es gelte \(\sum_{j=0}^{k}\binom{k}{j}=2^k\). Für die Summe bei \(k+1\) werden die Randterme getrennt und für \(1\le j\le k\) die Pascalsche Formel verwendet. 3. Damit ist \(\sum_{j=0}^{k+1}\binom{k+1}{j}=\sum_{j=0}^{k}\binom{k}{j}+\sum_{j=0}^{k}\binom{k}{j}=2^k+2^k=2^{k+1}\).

Antwort

Für alle \(n\ge 0\) gilt \(\sum_{j=0}^{n}\binom{n}{j}=2^n\).

43796212

Beweise mit vollständiger Induktion und der Pascalschen Formel: \(\sum_{j=0}^{n}\binom{n}{j}3^j=4^n\) für alle \(n\ge 0\).

Denkanstöße

- Zerlege die Koeffizienten der nächsten Zeile mithilfe ihrer beiden Vorgänger. - Verschiebe in einer der entstehenden Summen den Index sorgfältig. - Suche danach einen gemeinsamen Faktor.

Lösung

1. Für \(n=0\) gilt \(1=1\). 2. Es gelte \(\sum_{j=0}^{k}\binom{k}{j}3^j=4^k\). Mit der Pascalschen Formel und getrennt behandelten Randtermen gilt \(\sum_{j=0}^{k+1}\binom{k+1}{j}3^j=\sum_{j=0}^{k}\binom{k}{j}3^j+\sum_{j=1}^{k+1}\binom{k}{j-1}3^j\). 3. Mit der Indexverschiebung \(r=j-1\) wird die zweite Summe zu \(3\sum_{r=0}^{k}\binom{k}{r}3^r\). Nach der Induktionsvoraussetzung ergibt sich \(4^k+3\cdot 4^k=4^{k+1}\).

Antwort

Für alle \(n\ge 0\) gilt \(\sum_{j=0}^{n}\binom{n}{j}3^j=4^n\).

43796512

Eine Summe \(S_n\) erfüllt \(S_1=7\) und \(S_{n+1}-S_n=8n+7\). Bestimme eine Formel der Form \(S_n=an^2+bn\) und beweise sie anschließend durch vollständige Induktion.

Denkanstöße

- Vergleiche zunächst die Veränderung der gesuchten Formel mit der gegebenen Veränderung. - Nutze danach die rekursive Beziehung im Induktionsschritt.

Lösung

1. Aus \(S_1=7\) folgt \(a+b=7\). Außerdem ist \(S_{n+1}-S_n=a(2n+1)+b=8n+7\), also \(2a=8\) und \(a+b=7\). Damit ist \(a=4\) und \(b=3\). 2. Für \(n=1\) gilt \(S_1=7=4+3\). 3. Aus \(S_k=4k^2+3k\) folgt \(S_{k+1}=S_k+8k+7=4(k+1)^2+3(k+1)\).

Antwort

Es gilt \(S_n=4n^2+3n\), also \(a=4\) und \(b=3\).

43799112

Beweise für alle \(n\ge 1\): \(\sum_{j=1}^{n}\frac{1}{\sqrt{j}}\ge \sqrt{n}\).

Denkanstöße

- Vergleiche den neuen Summanden mit der Zunahme der rechten Seite. - Eine Differenz von Wurzeln lässt sich in eine günstigere Form bringen.

Lösung

1. Für \(n=1\) gilt \(1=1\). 2. Es gelte die Ungleichung für \(k\). Dann ist die nächste Summe mindestens \(\sqrt{k}+\frac{1}{\sqrt{k+1}}\). 3. Es genügt \(\frac{1}{\sqrt{k+1}}\ge \sqrt{k+1}-\sqrt{k}\). Nach Rationalisieren ist die rechte Seite \(\frac{1}{\sqrt{k+1}+\sqrt{k}}\), die nicht größer als \(\frac{1}{\sqrt{k+1}}\) ist.

Antwort

Für alle \(n\ge 1\) gilt \(\sum_{j=1}^{n}\frac{1}{\sqrt{j}}\ge \sqrt{n}\).

43799312

Beweise die Bernoulli-Ungleichung \((1+x)^n\ge 1+nx\) für alle \(n\ge 0\) und alle reellen \(x\ge -1\).

Denkanstöße

- Prüfe vor einer Multiplikation, welches Vorzeichen der Faktor hat. - Im ausmultiplizierten Ausdruck bleibt ein nichtnegativer Zusatz übrig.

Lösung

1. Für \(n=0\) gilt \(1=1\). 2. Es gelte \((1+x)^k\ge 1+kx\). Da \(1+x\ge 0\), darf mit \(1+x\) multipliziert werden: \((1+x)^{k+1}\ge (1+kx)(1+x)=1+(k+1)x+kx^2\). 3. Wegen \(kx^2\ge 0\) folgt \((1+x)^{k+1}\ge 1+(k+1)x\).

Antwort

Für alle \(n\ge 0\) und \(x\ge -1\) gilt \((1+x)^n\ge 1+nx\).

43799912

Beweise für alle \(n\ge 0\) und \(0\le x\le 1\): \((1+x)^n\le 1+(2^n-1)x\).

Denkanstöße

- Nutze neben der Induktionsvoraussetzung auch die Einschränkung des Parameters. - Nach dem Ausmultiplizieren muss ein quadratischer Term abgeschätzt werden.

Lösung

1. Für \(n=0\) gilt \(1=1\). 2. Es gelte die Ungleichung für \(k\). Multiplikation mit \(1+x\ge 0\) liefert \((1+x)^{k+1}\le 1+2^kx+(2^k-1)x^2\). 3. Wegen \(x^2\le x\) folgt \((1+x)^{k+1}\le 1+(2^{k+1}-1)x\).

Antwort

Für alle \(n\ge 0\) und \(0\le x\le 1\) gilt \((1+x)^n\le 1+(2^n-1)x\).

43800912

Eine Treppe mit \(n\) Stufen wird in Schritten der Länge \(1\) oder \(2\) hinaufgegangen. Sei \(W_n\) die Anzahl der möglichen Schrittfolgen. Beweise mit starker Induktion, dass \(W_n=F_{n+1}\), wobei \(F_1=1\), \(F_2=1\) und \(F_{n+2}=F_{n+1}+F_n\).

Denkanstöße

- Ordne alle Möglichkeiten nach ihrem letzten Schritt. - Für den Übergang werden zwei vorherige Fälle benötigt. - Prüfe deshalb zwei Anfangswerte.

Lösung

1. Für \(n=1\) gibt es \(W_1=1=F_2\), für \(n=2\) gibt es \(W_2=2=F_3\). 2. Es gelte für ein \(k\ge 2\) und alle \(m\) mit \(1\le m\le k\), dass \(W_m=F_{m+1}\). Jede Schrittfolge zu \(k+1\) endet mit einem Einzelschritt nach einer Folge zu \(k\) oder mit einem Doppelschritt nach einer Folge zu \(k-1\). Daher ist \(W_{k+1}=W_k+W_{k-1}\). 3. Mit den Induktionsannahmen folgt \(W_{k+1}=F_{k+1}+F_k=F_{k+2}\).

Antwort

Für alle \(n\ge 1\) gilt \(W_n=F_{n+1}\).

43801512

Beweise durch vollständige Induktion: Ein konvexes \(n\)-Eck besitzt für \(n\ge 3\) genau \(\frac{n(n-3)}{2}\) Diagonalen.

Denkanstöße

- Vergleiche ein Vieleck mit einem Vieleck, das genau einen Eckpunkt mehr besitzt. - Zähle sorgfältig neue Verbindungen und eine mögliche Statusänderung einer alten Seite.

Lösung

1. Ein Dreieck besitzt \(0=\frac{3\cdot 0}{2}\) Diagonalen. 2. Es gelte die Formel für ein konvexes \(k\)-Eck. Füge außerhalb nahe einer Seite einen neuen Eckpunkt so ein, dass ein konvexes \((k+1)\)-Eck entsteht. Vom neuen Eckpunkt gehen \(k-2\) neue Diagonalen aus; außerdem wird die ersetzte alte Seite zu einer Diagonale. Insgesamt kommen \(k-1\) Diagonalen hinzu. 3. Daher ist \(\frac{k(k-3)}{2}+k-1=\frac{(k+1)(k-2)}{2}\).

Antwort

Ein konvexes \(n\)-Eck besitzt genau \(\frac{n(n-3)}{2}\) Diagonalen.

43801712

Geraden liegen in allgemeiner Lage: Keine zwei sind parallel und keine drei gehen durch denselben Punkt. Beweise, dass \(n\) solche Geraden die Ebene in genau \(1+\frac{n(n+1)}{2}\) Gebiete zerlegen.

Denkanstöße

- Zähle nicht alle Gebiete neu, sondern nur die beim Hinzufügen einer Geraden entstehenden. - Entscheidend ist, in wie viele Abschnitte die neue Gerade zerlegt wird.

Lösung

1. Für \(n=0\) gibt es \(1\) Gebiet. 2. Es gelte, dass \(k\) Geraden \(1+\frac{k(k+1)}{2}\) Gebiete erzeugen. Eine neue Gerade schneidet die bisherigen \(k\) Geraden in \(k\) verschiedenen Punkten und wird dadurch in \(k+1\) Abschnitte zerlegt. Jeder Abschnitt teilt genau ein bestehendes Gebiet. 3. Daher wächst die Gebietszahl um \(k+1\): \(1+\frac{k(k+1)}{2}+k+1=1+\frac{(k+1)(k+2)}{2}\).

Antwort

Die Anzahl der Gebiete ist \(1+\frac{n(n+1)}{2}\).

43802312

Für \(f(x)=x^2e^x\) beweise durch vollständige Induktion: \(f^{(n)}(x)=\left(x^2+2nx+n(n-1)\right)e^x\) für alle \(n\ge 0\).

Denkanstöße

- Trenne beim Ableiten den Polynomfaktor vom Exponentialfaktor. - Ordne anschließend nach Potenzen von \(x\). - Vergleiche die konstanten Terme für zwei aufeinanderfolgende Indizes.

Lösung

1. Für \(n=0\) ergibt die Formel \(x^2e^x\). 2. Es gelte die Formel für \(k\). Beim Ableiten des Produkts entsteht die Summe aus der Ableitung des quadratischen Faktors und dem Faktor selbst. 3. Daher ist der neue Polynomfaktor \(2x+2k+x^2+2kx+k(k-1)=x^2+2(k+1)x+k(k+1)\), also die Formel für \(k+1\).

Antwort

Für alle \(n\ge 0\) gilt \(f^{(n)}(x)=\left(x^2+2nx+n(n-1)\right)e^x\).

43802612

Beweise für alle \(n\ge 0\), dass \(4^n+24n-1\) durch \(9\) teilbar ist.

Denkanstöße

- Vergleiche die beiden aufeinanderfolgenden Ausdrücke. - Im verbleibenden Zusatz kann eine einfachere Teilbarkeit genügen.

Lösung

1. Für \(n=0\) ist der Ausdruck \(0\). 2. Es sei \(4^k+24k-1\) durch \(9\) teilbar. Der nächste Ausdruck ist der alte Ausdruck plus \(3\cdot 4^k+24=3(4^k+8)\). 3. Da \(4\equiv 1\pmod{3}\), gilt \(4^k\equiv 1\pmod{3}\). Somit ist \(4^k+8\) durch \(3\) und der Zusatz durch \(9\) teilbar.

Antwort

Für alle \(n\ge 0\) gilt \(9\mid(4^n+24n-1)\).

Alle Aufgaben dürfen für Schule und Nachhilfe (auch im Rahmen bezahlter Nachhilfe) kostenlos genutzt, kopiert und ausgedruckt werden. Nicht gestattet sind kommerzielle Bearbeitungen sowie die Veröffentlichung oder Weiterverbreitung im Internet.