Binomialkoeffizient und Induktion

Question

Aufgabe:

Man zeige für alle natürlichen Zahlen n>=1 gilt

$$\sum_{k=0}^n \binom{2n}{2k}= 2^{2n-1}$$

Problem/Ansatz:

Der Induktionsanfang ist mir klar

Aber es hängt bei mir mal wieder beim Induktionsschritt

Ich würde wie folgt beginnen

$$\sum_{k=0}^{n+1} \binom{2n}{2k} = \sum_{k=0}^n \binom{2n}{2k} + \binom{(2(n+1)}{2k}$$

Stimmt das überhaupt?

Danach wendet man ja die Induktionsvoraussetzung an aber wie geht es dann weiter?

Comments

Du musst für den Induktionsschritt überall n durch n+1 ersetzen. Also auch im Binomialkoeffizienten.

Ist es denn zwingend, Induktion zu benutzen? Man kann das auch anders schnell zeigen.

Answer 1

Hier ist eine direkte Berechnung:

Per Binomialformel haben wir:

$$2^{2n} = (1+1)^{2n} = \sum_{i=0}^{2n}\binom{2n}{i}$$$$0^{2n} = (1-1)^{2n} = \sum_{i=0}^{2n}(-1)^i\binom{2n}{i}$$Addieren gibt$$2^{2n} = \sum_{i=0}^{2n}(1+(-1)^i)\binom{2n}{i}\stackrel{i=2k}{=} 2\sum_{k=0}^{n}\binom{2n}{2k}$$Daraus folgt die Behauptung.

Answer 2

Hier auch eine direkte Herleitung

$$\sum_{k=0}^{n} \binom{2n}{2k} \newline = \sum_{k=0}^n \left( \binom{2n - 1}{2k} + \binom{2n - 1}{2k - 1} \right) \newline = \sum_{k=-1}^{2n} \binom{2n - 1}{k} \newline = \sum_{k=0}^{2n - 1} \binom{2n - 1}{k} \newline = (1 + 1)^{2n-1} \newline = 2^{2n-1}$$

Answer 3

Es ist bekanntlich $\sum_{k=0}^{2n}{{2n}\choose {k}}=2^{2n}$.

Das ist die Anzahl aller Teilmengen einer $2n$-elementigen Menge.

Nun kann man zeigen, dass die Hälfte dieser Teilmengen

eine gerade Anzahl von Elementen (=2k) besitzt, oder

anders ausgedrückt, dass es genau so viele

Teilmengen mit ungerad-vielen Elementen wie

Teilmengen mit gerad-vielen Elementen gibt.