Antwort mit KI erzeugt
Lösung:
Um zu zeigen, dass für alle \(n \in \mathbb{N}_0\)
\(F_{n+1} = \sum_{i=0}^{n} \binom{n-i}{i}\)
gilt, verwenden wir den Induktionsbeweis.
Induktionsanfang (IA): Für \(n=0\),
\(F_{0+1} = F_1 = 1\)
und
\(\sum_{i=0}^{0} \binom{0-i}{i} = \binom{0}{0} = 1\)
Somit gilt die Behauptung für \(n=0\).
Induktionsschritt:
Induktionsvoraussetzung (IV): Die Behauptung gelte für ein beliebiges, aber festes \(n \in \mathbb{N}_0\). Das bedeutet:
\(F_{n+1} = \sum_{i=0}^{n} \binom{n-i}{i}\)
Induktionsbehauptung (IB): Es ist zu zeigen, dass:
\(F_{(n+1)+1} = \sum_{i=0}^{n+1} \binom{(n+1)-i}{i}\)
Induktionsschritt (IS):
Wir wissen, dass \(F_{n+2} = F_{n+1} + F_{n}\). Wir setzen die Induktionsvoraussetzung ein und erhalten:
\(F_{n+2} = \sum_{i=0}^{n} \binom{n-i}{i} + \sum_{i=0}^{n-1} \binom{(n-1)-i}{i}\)
Nun müssen wir zeigen, dass diese Summe gleich der rechten Seite der Induktionsbehauptung ist:
\(\sum_{i=0}^{n+1} \binom{(n+1)-i}{i}\)
Beachten wir, dass die aufsummierten Binomialkoeffizienten der Pascal'schen Regel entsprechen:
\(\binom{n}{i} + \binom{n}{i-1} = \binom{n+1}{i}\)
Wir transformieren die Summen, indem wir die Indizes passend anpassen und ausnutzen, dass \(\binom{n}{k} = 0\) für \(n < k\):
\(\sum_{i=0}^{n} \binom{n-i}{i} + \sum_{i=0}^{n+1} \binom{n-(i-1)}{i-1} = \sum_{i=0}^{n+1} \left( \binom{n-i}{i} + \binom{n-i+1}{i-1} \right)\)
Nun wenden wir die Pascal'sche Regel auf jeden Term an:
\(\sum_{i=0}^{n+1} \binom{(n+1)-i}{i}\)
Damit ist die Induktionsbehauptung bewiesen, und es folgt, dass für alle \(n \in \mathbb{N}_0\),
\(F_{n+1} = \sum_{i=0}^{n} \binom{n-i}{i}\)
gilt.
