Summen, Produkte und vollständige Induktion – Mathe Studium 1. Semester Arbeitsblatt Lösungen zum Herunterladen als PDF

← Zurück zu den Aufgaben

1. Lösung zu Aufgabe 1

   a) \(1+4+9+16+25=55\).
   b) \(1+2+4+8+16=31=2^5-1\).
   c) \(-1+2-3+4=2\).
   d) \(1\cdot2\cdot3\cdot4\cdot5=120=5!\).
   e) \(\frac21\cdot\frac32\cdot\frac43\cdot\frac54=5\) (Teleskopprodukt: alles kürzt sich bis auf \(\frac51\)).

   Erläuterung: Beim Ausschreiben setzt man den Laufindex nacheinander für jeden Wert zwischen unterer und oberer Grenze ein und verknüpft die Ergebnisse mit Plus bzw. Mal. Bei der Summe in b) erkennt man die geometrische Summenformel wieder, beim letzten Produkt kürzt sich jeder Zähler mit dem folgenden Nenner. Solche Kontrollen mit kleinen Zahlen sollte man vor jedem allgemeinen Beweis durchführen.

2. Lösung zu Aufgabe 2

   a) \(\sum_{k=1}^{50}(2k-1)=2\cdot\frac{50\cdot51}2-50=2550-50=2500=50^2\).
   b) \(\sum_{k=1}^{10}2^k=2^{11}-2=2046\).
   c) Die Nenner sind \(k(k+1)\) mit \(k=1,\dots,9\) (\(9\cdot10=90\)): \(\sum_{k=1}^9\frac1{k(k+1)}=\sum_{k=1}^9\left(\frac1k-\frac1{k+1}\right)=1-\frac1{10}=\frac9{10}\).

   Erläuterung: Entscheidend ist, ein Bildungsgesetz für das \(k\)-te Glied zu finden und die Grenzen so zu wählen, dass erstes und letztes Glied stimmen. Prüfen Sie das immer, indem Sie \(k\) gleich der unteren und der oberen Grenze einsetzen. Danach helfen die bekannten Formeln: Gaußsche Summe, geometrische Summe und Teleskopsumme. Ein Fehler um eins bei den Grenzen ist der häufigste Fehler.

3. Lösung zu Aufgabe 3

   a) \(j\) läuft von \(1\) bis \(8\): \(\sum_{j=1}^8j^2=\frac{8\cdot9\cdot17}6=204\).
   b) Mit \(j=k+1\) wird die zweite Summe zu \(\sum_{j=1}^nj\); die Differenz ist \(0\).
   c) \(\sum_{k=1}^na_{k+1}=\sum_{j=2}^{n+1}a_j\). Also \(\sum_{j=2}^{n+1}a_j-\sum_{k=1}^na_k=a_{n+1}-a_1\), da die Summanden \(a_2,\dots,a_n\) in beiden Summen vorkommen.

   Erläuterung: Bei einer Indexverschiebung ändert sich nur die Bezeichnung, nicht die Summe. Wer \(j=k-2\) setzt, muss auch die Grenzen umrechnen: Aus \(k=3\) wird \(j=1\), aus \(k=10\) wird \(j=8\).

4. Lösung zu Aufgabe 4

   a) \(\frac{100\cdot101}2=5050\).
   b) \(\frac{20\cdot21\cdot41}6=2870\).
   c) \(\left(\frac{10\cdot11}2\right)^2=55^2=3025\); dasselbe wie das Quadrat der Summe.
   d) \(6\cdot\frac{n(n+1)(2n+1)}6-2\cdot\frac{n(n+1)}2=n(n+1)(2n+1-1)=2n^2(n+1)\).

   Erläuterung: Man setzt einfach \(n\) in die Formeln ein und rechnet sorgfältig. In d) zerlegt man die Summe zuerst mit der Linearität in zwei Standardsummen, klammert dann den gemeinsamen Faktor \(n(n+1)\) aus und vereinfacht die verbleibende Klammer. Eine Kontrolle mit \(n=1\) zeigt: Links steht \(6-2=4\), rechts \(2\cdot1\cdot2=4\). Die Formel ist also plausibel.

5. Lösung zu Aufgabe 5

   a) \(\frac{7\cdot6\cdot5}{3\cdot2\cdot1}=35\); \(\binom{10}8=\binom{10}2=\frac{10\cdot9}2=45\).
   b) \(n\) (ein Element auswählen), \(\frac{n(n-1)}2\) (Paare; jedes Paar wird bei geordneter Auswahl zweimal gezählt).
   c) \(1,6,15,20,15,6,1\); Summe \(64=2^6\).
   d) \(\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}=\frac{n!\,(n-k+1)+n!\,k}{k!(n-k+1)!}=\frac{(n+1)!}{k!(n+1-k)!}\).

   Erläuterung: Zum Berechnen kürzt man vor dem Ausmultiplizieren: Im Zähler stehen nur so viele absteigende Faktoren, wie der untere Eintrag angibt. Die Symmetrie spart Rechenarbeit, wenn der untere Eintrag größer als die Hälfte ist. Die Pascal-Rekursion erklärt, warum jede Zahl im Dreieck die Summe der beiden darüberstehenden ist.

6. Lösung zu Aufgabe 6

   a) \(x^4+4\cdot2x^3+6\cdot4x^2+4\cdot8x+16=x^4+8x^3+24x^2+32x+16\).
   b) Glied \(\binom53(2x)^3(-1)^2=10\cdot8x^3\): Koeffizient \(80\).
   c) \(1+5\cdot0{,}01+10\cdot0{,}0001=1{,}051\). Fehler etwa \(10^{-5}\).
   d) \(0=(1-1)^n=\sum_{k=0}^n\binom nk1^{n-k}(-1)^k\).

   Erläuterung: Im binomischen Satz enthält jedes Glied einen Binomialkoeffizienten, eine Potenz des ersten und eine Potenz des zweiten Summanden; die Exponenten ergeben zusammen immer \(n\). Vorzeichen und Faktoren wie die \(2\) in \(2x\) muss man mitpotenzieren. Die Näherung in c) zeigt, warum man bei kleinen Zahlen oft nur die ersten Glieder braucht: Die weiteren Glieder sind winzig.

7. Lösung zu Aufgabe 7

   a) \(\sum_{k=1}^{10}k^2=\frac{10\cdot11\cdot21}6=385\).
   b) \(\frac{n(n+1)(2n+1)}6=140\): Probieren mit \(n=7\): \(\frac{7\cdot8\cdot15}6=140\). Also \(7\) Lagen.
   c) \(1+3+6+10+15+21=56\).
   d) \(\frac12\left(\frac{n(n+1)(2n+1)}6+\frac{n(n+1)}2\right)=\frac{n(n+1)}{12}(2n+1+3)=\frac{n(n+1)(n+2)}6\). Für \(n=6\): \(56\).

   Erläuterung: Jede Lage einer Pyramide ist eine geometrische Figur, deren Orangenzahl man kennt: ein Quadrat mit \(k^2\) oder ein Dreieck mit \(\frac{k(k+1)}2\) Orangen. Die Gesamtzahl ist deshalb eine Summe über alle Lagen. In b) muss man eine kubische Gleichung lösen; systematisches Probieren mit kleinen natürlichen Zahlen ist hier der schnellste Weg.

8. Lösung zu Aufgabe 8

   a) \(K_n=\sum_{k=1}^n600\cdot1{,}02^k\).
   b) \(K_n=600\cdot1{,}02\cdot\frac{1{,}02^n-1}{0{,}02}\).
   c) \(K_{18}\approx13\,104{,}34\) €. Eingezahlt wurden \(10\,800\) €, Zinsen etwa \(2304{,}34\) €.
   d) IA: \(q=q\frac{q-1}{q-1}\). IS: \(q\frac{q^n-1}{q-1}+q^{n+1}=q\frac{q^n-1+q^n(q-1)}{q-1}=q\frac{q^{n+1}-1}{q-1}\).

   Erläuterung: Jede Einzahlung wächst unabhängig von den anderen mit dem Zinseszins. Die früheste Einzahlung liegt am längsten auf dem Konto und wird daher am häufigsten mit \(1{,}02\) multipliziert. Addiert man alle Beiträge, entsteht eine geometrische Summe. Der Zinsanteil ist klein, weil der Zinssatz niedrig ist; bei längeren Laufzeiten wächst er deutlich.

9. Lösung zu Aufgabe 9

   a) Letztes Feld \(2^{63}\approx9{,}2\cdot10^{18}\); insgesamt \(2^{64}-1=18\,446\,744\,073\,709\,551\,615\approx1{,}8\cdot10^{19}\).
   b) IA \(n=1\): \(1=2-1\). IS: \(\sum_{k=0}^n2^k=(2^n-1)+2^n=2^{n+1}-1\).
   c) \(1{,}84\cdot10^{19}\cdot0{,}025\) g \(\approx4{,}6\cdot10^{17}\) g \(=4{,}6\cdot10^{11}\) t.
   d) \(\frac{4{,}6\cdot10^{11}}{5\cdot10^8}\approx922\) Jahre.

   Erläuterung: Die Verdopplung von Feld zu Feld erzeugt exponentielles Wachstum. Schon nach zehn Feldern sind es über tausend Körner, nach zwanzig über eine Million. Die Summe aller Felder ist nur um eins kleiner als die Körnerzahl, die ein fünfundsechzigstes Feld hätte. Das ist der Kern der Formel \(2^n-1\).

10. Lösung zu Aufgabe 10

    a) \(\binom n2=\frac{n(n-1)}2\) ungeordnete Paare.
    b) \(2\cdot\binom{18}2=2\cdot153=306\) Spiele, \(\frac{306}9=34\) Spieltage.
    c) \(\binom{30}2=435\).
    d) Kommt die zweite Person, gibt es \(1\) Handschlag, die dritte \(2\), …, die \(n\)-te \(n-1\). Insgesamt \(1+2+\dots+(n-1)\), und das ist die Zahl aller Paare.

    Erläuterung: Paarungen sind ungeordnete Auswahlen von zwei Mannschaften; Hin- und Rückspiel verdoppeln die Anzahl.

11. Lösung zu Aufgabe 11

    a) \(\binom{10}3=120\).
    b) Für jede Zutat zwei Möglichkeiten: \(2^{10}=1024\). Oder \(\sum_{k=0}^{10}\binom{10}k=2^{10}\).
    c) \(1+10+45+120=176\).
    d) Salami ist fest, zwei weitere aus neun: \(\binom92=36\).

    Erläuterung: Die Reihenfolge, in der die Zutaten genannt werden, spielt keine Rolle; deshalb zählen Binomialkoeffizienten. In b) gibt es zwei Zählweisen, die dasselbe Ergebnis liefern müssen – das ist ein kombinatorischer Beweis der Formel \(\sum\binom nk=2^n\). In d) wird eine Wahl festgelegt und nur noch der Rest gewählt.

12. Lösung zu Aufgabe 12

    a) \(1\), \(3\), \(7\).
    b) Die größte Scheibe kann erst bewegt werden, wenn alle anderen auf dem Hilfsstab liegen (\(T_{n-1}\) Züge). Dann ein Zug, danach wieder \(T_{n-1}\) Züge.
    c) IA: \(T_1=1=2^1-1\). IS: \(T_{n+1}=2(2^n-1)+1=2^{n+1}-1\).
    d) \(2^{20}-1=1\,048\,575\) Sekunden, das sind etwa \(12{,}1\) Tage.

    Erläuterung: Die Rekursion beschreibt die beste Strategie; die Induktion bestätigt die geschlossene Formel.

13. Lösung zu Aufgabe 13

    a) \(n^2\): \(1,4,9,16,25,36\); \(2^n\): \(2,4,8,16,32,64\).
    b) IA: \(32>25\). IS: \(2^{n+1}=2\cdot2^n>2n^2=n^2+n^2>n^2+2n+1=(n+1)^2\).
    c) Für \(n=3\) ist \(8<9\), für \(n=4\) gilt Gleichheit \(16=16\).
    d) \(2^{40}\) ms \(\approx34{,}8\) Jahre.

    Erläuterung: Die Tabelle zeigt, dass die Exponentialfunktion anfangs nicht immer vorne liegt; erst ab \(n=5\) überholt sie die Potenz endgültig. Deshalb beginnt die Induktion bei \(n_0=5\). In der Informatik bedeutet das: Ein Algorithmus mit exponentieller Laufzeit wird für große Eingaben unbrauchbar, egal wie schnell der Rechner ist.

14. Lösung zu Aufgabe 14

    a) \(1,1,2,3,5,8,13,21,34,55,89,144\).
    b) IA: \(F_1=1=F_3-1\). IS: \(\sum_{k=1}^{n+1}F_k=F_{n+2}-1+F_{n+1}=F_{n+3}-1\).
    c) \(1+1+2+3+5+8+13+21+34+55=143=F_{12}-1\).
    d) IA: \(F_1^2=1=F_1F_2\). IS: \(F_nF_{n+1}+F_{n+1}^2=F_{n+1}(F_n+F_{n+1})=F_{n+1}F_{n+2}\).

    Erläuterung: Bei Fibonacci-Beweisen benutzt man im Induktionsschritt die Rekursion \(F_{n+2}=F_{n+1}+F_n\), um zwei aufeinanderfolgende Glieder zusammenzufassen. In b) wird so aus \(F_{n+2}+F_{n+1}\) das Glied \(F_{n+3}\), in d) aus \(F_n+F_{n+1}\) das Glied \(F_{n+2}\). Die Formeln lassen sich gut an der Liste aus a) kontrollieren.

15. Lösung zu Aufgabe 15

    a) \(\sum_{k=1}^nk^3=\left(\sum_{k=1}^nk\right)^2\).
    b) IA: \(1=\frac{1\cdot4}4\). IS: \(\frac{n^2(n+1)^2}4+(n+1)^3=\frac{(n+1)^2(n^2+4n+4)}4=\frac{(n+1)^2(n+2)^2}4\).
    c) \(\left(\frac{20\cdot21}2\right)^2-\left(\frac{10\cdot11}2\right)^2=44\,100-3025=41\,075\).
    d) Das Quadrat mit Seite \(1+2+\dots+n\) zerfällt in Winkelhaken. Der \(k\)-te Haken hat die Fläche \(\left(\frac{k(k+1)}2\right)^2-\left(\frac{(k-1)k}2\right)^2=k^3\).

    Erläuterung: Im Induktionsschritt klammert man \((n+1)^2\) aus: \(\frac{(n+1)^2}4\left(n^2+4(n+1)\right)\), und die Klammer ist das Quadrat \((n+2)^2\). In c) bildet man die Differenz zweier Summen, statt alle zehn Kubikzahlen einzeln zu addieren.

16. Lösung zu Aufgabe 16

    a) IA: \(3\mid3\). IS: \((n+1)^3+2(n+1)=(n^3+2n)+3(n^2+n+1)\); beide Summanden durch \(3\) teilbar.
    b) IA: \(27+8=35=5\cdot7\). IS: \(3^{2n+3}+2^{n+3}=9\cdot3^{2n+1}+2\cdot2^{n+2}=9(3^{2n+1}+2^{n+2})-7\cdot2^{n+2}\).
    c) IA: \(9-1=8\). IS: \(3^{2n+2}-1=9(3^{2n}-1)+8\).

    Erläuterung: Bei Teilbarkeitsbeweisen formt man den Ausdruck für \(n+1\) so um, dass der Ausdruck für \(n\) als Summand oder Faktor erscheint. Nach der Induktionsvoraussetzung ist er durch die Zahl teilbar; der Rest muss es offensichtlich sein. Wichtig ist, wirklich nur Summen von Vielfachen zu erzeugen.

17. Lösung zu Aufgabe 17

    a) Mit \(x=\frac1n\): \(\ge1+n\cdot\frac1n=2\).
    b) Mit \(x=0{,}01\), \(n=100\): \(\ge2\). Tatsächlich \(1{,}01^{100}\approx2{,}7048\).
    c) Mit \(x=-\frac1{n^2}\ge-1\): \(\ge1-\frac n{n^2}=1-\frac1n\).
    d) \(\frac{a_n}{a_{n-1}}\ge\left(1-\frac1n\right)\frac n{n-1}=1\). Also \(a_n\ge a_{n-1}\). Der Grenzwert dieser monotonen Folge ist \(e\).

    Erläuterung: Die Bernoullische Ungleichung ersetzt eine schwer berechenbare Potenz durch einen einfachen linearen Ausdruck. Sie ist grob, reicht aber oft aus, um Schranken und Monotonie zu zeigen.

18. Lösung zu Aufgabe 18

    a) \(8=3+5\), \(9=3+3+3\), \(10=5+5\).
    b) Ist \(n\ge11\), so ist \(n-3\ge8\) bereits darstellbar; eine \(3\)-Cent-Marke mehr ergibt \(n\).
    c) Mit \(5\)-Cent-Marken bleiben \(7\) oder \(2\) Cent, beide nicht durch \(3\) teilbar.
    d) \(n=2\) ist prim. Ist \(n\) prim, fertig. Sonst \(n=ab\) mit \(2\le a,b<n\); nach Voraussetzung sind \(a\) und \(b\) Produkte von Primzahlen, also auch \(n\).

19. Lösung zu Aufgabe 19

    a) \(p_1=\frac24=\frac12\), \(p_2=\frac6{16}=\frac38=\frac12\cdot\frac34\), \(p_3=\frac{20}{64}=\frac5{16}=\frac38\cdot\frac56\).
    b) \(\binom{2n+2}{n+1}=\binom{2n}n\cdot\frac{(2n+2)(2n+1)}{(n+1)^2}\), also \(p_{n+1}=p_n\cdot\frac{(2n+2)(2n+1)}{4(n+1)^2}=p_n\cdot\frac{2n+1}{2n+2}\). Mit IA \(p_1=\frac12\) folgt die Produktformel.
    c) IA: \(\frac12\le\frac12\). Ausmultiplizieren: links \(12n^3+28n^2+19n+4\), rechts \(12n^3+28n^2+20n+4\); die Ungleichung gilt. Damit \(p_{n+1}\le\frac1{\sqrt{3n+1}}\cdot\frac{2n+1}{2n+2}\le\frac1{\sqrt{3n+4}}\).
    d) \(p_{10}=\frac{184\,756}{1\,048\,576}\approx0{,}1762\), Schranke \(\frac1{\sqrt{31}}\approx0{,}1796\). Genau \(10\)-mal Kopf bei \(20\) Würfen kommt nur in etwa \(18\,\%\) der Fälle vor, obwohl es das wahrscheinlichste Ergebnis ist.

20. Lösung zu Aufgabe 20

    a) Beim Schritt von \(n=1\) auf \(n=2\): Die beiden Gruppen „ohne erstes“ und „ohne letztes“ Pferd haben kein gemeinsames Pferd, man kann die Farben nicht verbinden.
    b) Wählt man \(k\) Frauen, so müssen \(n-k\) Männer dazu: \(\binom nk\binom n{n-k}=\binom nk^2\) Möglichkeiten. Summiert über \(k\) ergibt das alle \(\binom{2n}n\) Teams.
    c) \(1+16+36+16+1=70=\binom84\).
    d) \(n(1+x)^{n-1}=\sum_{k=1}^nk\binom nkx^{k-1}\); für \(x=1\) folgt die Behauptung.