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

Schreiben Sie die Summen und Produkte aus und berechnen Sie sie.

a) \(\sum_{k=1}^5k^2\)
b) \(\sum_{k=0}^42^k\)
c) \(\sum_{k=1}^4(-1)^kk\)
d) \(\prod_{k=1}^5k\)
e) \(\prod_{k=1}^4\left(1+\frac1k\right)\)

Schreiben Sie mit dem Summenzeichen und berechnen Sie den Wert.

a) \(1+3+5+\dots+99\)
b) \(2+4+8+\dots+1024\)
c) \(\frac12+\frac16+\frac1{12}+\dots+\frac1{90}\)

Formen Sie mit einer Indexverschiebung um.

a) Berechnen Sie \(\sum_{k=3}^{10}(k-2)^2\), indem Sie \(j=k-2\) setzen.
b) Zeigen Sie \(\sum_{k=1}^nk-\sum_{k=0}^{n-1}(k+1)=0\).
c) Zeigen Sie \(\sum_{k=1}^n(a_{k+1}-a_k)=a_{n+1}-a_1\) mit einer Indexverschiebung.

Berechnen Sie mit den Summenformeln.

a) \(\sum_{k=1}^{100}k\)
b) \(\sum_{k=1}^{20}k^2\)
c) \(\sum_{k=1}^{10}k^3\); vergleichen Sie mit \(\left(\sum_{k=1}^{10}k\right)^2\).
d) \(\sum_{k=1}^n(6k^2-2k)\) in faktorisierter Form

Berechnen Sie und begründen Sie kombinatorisch.

a) \(\binom73\) und \(\binom{10}8\)
b) \(\binom n1\) und \(\binom n2\)
c) Die sechste Zeile des Pascalschen Dreiecks
d) Zeigen Sie \(\binom{n+1}k=\binom nk+\binom n{k-1}\) durch Rechnen mit Fakultäten.

Wenden Sie den binomischen Satz an.

a) Multiplizieren Sie \((x+2)^4\) aus.
b) Bestimmen Sie den Koeffizienten von \(x^3\) in \((2x-1)^5\).
c) Nähern Sie \(1{,}01^5\) mit den ersten drei Gliedern von \((1+0{,}01)^5\) und vergleichen Sie mit dem genauen Wert \(1{,}0510100501\).
d) Zeigen Sie \(\sum_{k=0}^n(-1)^k\binom nk=0\) für \(n\ge1\).

Ein Händler stapelt Orangen zu Pyramiden. Bei einer quadratischen Pyramide liegt oben eine Orange, darunter \(2\times2\), dann \(3\times3\) und so weiter. Bei einer dreieckigen Pyramide liegen in der \(k\)-ten Lage von oben \(1+2+\dots+k\) Orangen.

a) Wie viele Orangen hat eine quadratische Pyramide mit \(10\) Lagen?
b) Wie viele Lagen hat eine quadratische Pyramide mit \(140\) Orangen?
c) Wie viele Orangen enthält eine dreieckige Pyramide mit \(6\) Lagen?
d) Zeigen Sie \(\sum_{k=1}^n\frac{k(k+1)}2=\frac{n(n+1)(n+2)}6\) mit den Summenformeln.

Eltern zahlen zu Beginn jedes Jahres \(600\) € auf ein Sparkonto, das mit \(2\,\%\) pro Jahr verzinst wird. Die erste Einzahlung wird also \(n\) Jahre verzinst, die letzte ein Jahr.

a) Schreiben Sie den Kontostand nach \(n\) Jahren mit dem Summenzeichen.
b) Bestimmen Sie eine geschlossene Formel mit der geometrischen Summenformel.
c) Wie hoch ist der Kontostand nach \(18\) Jahren? Wie viel davon sind Zinsen?
d) Begründen Sie die geometrische Summenformel \(\sum_{k=1}^nq^k=q\frac{q^n-1}{q-1}\) durch Induktion.

Auf das \(k\)-te Feld eines Schachbretts (\(k=1,\dots,64\)) werden \(2^{k-1}\) Reiskörner gelegt. Ein Reiskorn wiegt etwa \(0{,}025\) g; die Welt erntet jährlich rund \(5\cdot10^8\) Tonnen Reis.

a) Wie viele Körner liegen auf dem letzten Feld und wie viele insgesamt?
b) Beweisen Sie \(\sum_{k=0}^{n-1}2^k=2^n-1\) durch vollständige Induktion.
c) Wie viele Tonnen Reis sind das?
d) Wie viele Jahre Welternte entspricht das ungefähr?

In einer Fußballliga mit \(n\) Mannschaften spielt jede Mannschaft gegen jede andere einmal zu Hause und einmal auswärts.

a) Wie viele Paarungen gibt es bei \(n\) Mannschaften? Begründen Sie mit einem Binomialkoeffizienten.
b) Wie viele Spiele hat eine Saison der Bundesliga mit \(18\) Mannschaften? Wie viele Spieltage mit je \(9\) Spielen sind das?
c) Bei einem Treffen begrüßen sich \(30\) Personen paarweise mit Handschlag. Wie viele Handschläge gibt es?
d) Beweisen Sie \(\sum_{k=1}^{n-1}k=\binom n2\) kombinatorisch: Die neue Person Nummer \(k+1\) begrüßt alle, die schon da sind.

Eine Pizzeria bietet \(10\) verschiedene Zutaten an. Eine Pizza kann beliebig viele davon haben (auch keine).

a) Wie viele Pizzen mit genau drei Zutaten gibt es?
b) Wie viele verschiedene Pizzen gibt es insgesamt? Begründen Sie zwei Arten.
c) Wie viele Pizzen haben höchstens drei Zutaten?
d) Wie viele Pizzen mit genau drei Zutaten enthalten Salami?

Beim Spiel „Türme von Hanoi“ liegen \(n\) Scheiben auf einem von drei Stäben, die größte unten. Es darf immer nur eine Scheibe bewegt werden, und nie eine größere auf einer kleineren liegen. \(T_n\) sei die minimale Zugzahl.

a) Bestimmen Sie \(T_1,T_2,T_3\) durch Ausprobieren.
b) Begründen Sie die Rekursion \(T_n=2T_{n-1}+1\).
c) Beweisen Sie \(T_n=2^n-1\) durch Induktion.
d) Wie lange dauert das Spiel mit \(20\) Scheiben bei einem Zug pro Sekunde?

Programm A braucht für eine Eingabe der Größe \(n\) genau \(n^2\) Millisekunden, Programm B \(2^n\) Millisekunden.

a) Vergleichen Sie die Laufzeiten für \(n=1,\dots,6\) in einer Tabelle.
b) Beweisen Sie \(2^n>n^2\) für alle \(n\ge5\) durch Induktion. Verwenden Sie im Schritt \(2n+1<n^2\) für \(n\ge3\).
c) Warum gilt die Aussage nicht schon für \(n\ge3\)?
d) Wie lange braucht Programm B für \(n=40\)?

Die Fibonacci-Zahlen sind \(F_1=F_2=1\), \(F_{n+2}=F_{n+1}+F_n\). In Leonardo von Pisas Modell gibt \(F_n\) die Zahl der Kaninchenpaare im \(n\)-ten Monat an.

a) Berechnen Sie \(F_1,\dots,F_{12}\).
b) Beweisen Sie \(\sum_{k=1}^nF_k=F_{n+2}-1\) durch Induktion.
c) Prüfen Sie die Formel für \(n=10\).
d) Beweisen Sie \(\sum_{k=1}^nF_k^2=F_nF_{n+1}\).

Nikomachos von Gerasa bemerkte um 100 n. Chr., dass die Summe der ersten Kubikzahlen stets eine Quadratzahl ist.

a) Formulieren Sie die Vermutung, die die Tabelle nahelegt.
b) Beweisen Sie \(\sum_{k=1}^nk^3=\frac{n^2(n+1)^2}4\) durch Induktion.
c) Berechnen Sie \(11^3+12^3+\dots+20^3\).
d) Geben Sie eine anschauliche Deutung: \(k^3=k\cdot k^2\) sind \(k\) Quadrate mit Seite \(k\), die zusammen einen Winkelhaken des großen Quadrats bilden.

Beweisen Sie für alle \(n\in\mathbb N\) durch vollständige Induktion.

a) \(3\mid n^3+2n\)
b) \(7\mid3^{2n+1}+2^{n+2}\)
c) \(8\mid3^{2n}-1\)

Die Bernoullische Ungleichung lautet \((1+x)^n\ge1+nx\) für \(x\ge-1\), \(n\in\mathbb N\).

a) Folgern Sie \(\left(1+\frac1n\right)^n\ge2\).
b) Zeigen Sie \(1{,}01^{100}\ge2\) und vergleichen Sie mit dem Taschenrechnerwert.
c) Zeigen Sie \(\left(1-\frac1{n^2}\right)^n\ge1-\frac1n\).
d) Folgern Sie mit c), dass \(a_n=\left(1+\frac1n\right)^n\) monoton wachsend ist. Hinweis: \(\frac{a_n}{a_{n-1}}=\left(1-\frac1{n^2}\right)^n\cdot\frac n{n-1}\).

Bei der starken Induktion darf man im Schritt alle kleineren Fälle benutzen.

a) Zeigen Sie: Jeder Betrag von mindestens \(8\) Cent lässt sich mit \(3\)- und \(5\)-Cent-Marken genau bezahlen. Behandeln Sie \(8,9,10\) direkt.
b) Warum funktioniert der Schritt \(n\to n+3\)?
c) Zeigen Sie, dass \(7\) Cent nicht möglich sind.
d) Beweisen Sie mit starker Induktion: Jede natürliche Zahl \(n\ge2\) ist ein Produkt von Primzahlen.

Eine Münze wird \(2n\)-mal geworfen. Die Wahrscheinlichkeit, genau \(n\)-mal Kopf zu erhalten, ist \(p_n=\binom{2n}n\frac1{4^n}\). Man kann zeigen, dass \(p_n=\prod_{k=1}^n\frac{2k-1}{2k}\) gilt.

a) Berechnen Sie \(p_1,p_2,p_3\) auf beide Arten.
b) Beweisen Sie \(p_n=\prod_{k=1}^n\frac{2k-1}{2k}\) durch Induktion. Zeigen Sie dazu \(p_{n+1}=p_n\cdot\frac{2n+1}{2n+2}\) aus der Fakultätsdarstellung.
c) Beweisen Sie \(p_n\le\frac1{\sqrt{3n+1}}\) durch Induktion. Im Schritt ist \((2n+1)^2(3n+4)\le(2n+2)^2(3n+1)\) zu zeigen.
d) Berechnen Sie \(p_{10}\) und vergleichen Sie mit der Schranke. Was bedeutet das Ergebnis für \(20\) Würfe?

„Satz“: Alle Pferde haben dieselbe Farbe. „Beweis“ durch Induktion über die Anzahl \(n\) der Pferde in einer Gruppe: Für \(n=1\) ist das klar. Seien \(n+1\) Pferde gegeben. Nimmt man das erste weg, haben die übrigen \(n\) nach Voraussetzung dieselbe Farbe; nimmt man das letzte weg, ebenfalls. Also haben alle dieselbe Farbe.

a) Finden Sie den Fehler. Für welches \(n\) versagt der Schritt?
b) Beweisen Sie kombinatorisch \(\sum_{k=0}^n\binom nk^2=\binom{2n}n\): Aus \(n\) Frauen und \(n\) Männern wird ein Team von \(n\) Personen gebildet.
c) Prüfen Sie die Identität für \(n=4\).
d) Beweisen Sie \(\sum_{k=0}^nk\binom nk=n2^{n-1}\) durch Ableiten von \((1+x)^n\).