Beweis einer Aussage mit Summenformel und Binomialkoeffizient (mit binomischem Lehrsatz?)

Question

Aufgabe:

Beweis einer Aussage mit Summe (mit binomischem Lehrsatz?)

Problem/Ansatz:

Die Aussage (s. Formel) ist zu beweisen. Mein Ansatz war mit dem binomischen Lehrsatz bzw. in die Formel für den Binomialkoeffizienten einzusetzen aber was soll ich mit der Summe machen? Wäre dankbar für einen guten Ansatz :)

Text erkannt:

$\sum \limits_{k=0}^{n-q}\left(\begin{array}{c}n \\ k+q\end{array}\right)\left(\begin{array}{c}k+q \\ q\end{array}\right)=2^{n-q}\left(\begin{array}{l}n \\ q\end{array}\right)$

Comments

Ich würde erstmal das Produkt auflösen und kürzen.

Answer 1

Doppelzählstrategie kann hier auch helfen:

Zählung 1:
Anzahl der n-stelligen Zahlen aus den Ziffern 1,2,3 mit genau q 3er:

$$\underbrace{\binom nq}_{\text{wähle q Plätze für die 3er}} \cdot \underbrace{2^{n-q}}_{\text{restl. Plätze 1er oder 2er}}$$

Zählung 2:

Anzahl der n-stelligen Zahlen aus den Ziffern 1,2,3 mit genau q 3er und k = 0,...,n-q 2er:

$$\underbrace{\binom{n}{k+q}}_{\text{wähle k+q Plätze für die q 3er und k 2er}}\cdot \underbrace{\binom{k+q}{q}}_{\text{wähle q Plätze für die 3er aus den k+q Plätzen für 2er und 3er}}$$

Nun Summieren von k=0..n-q.

Ergänzung wg. Kommentar
Zur "summarischen Lösung" - erweitere jeden Summanden mit $(n-q)!$:
$$\sum\limits_{k=0}^{n-q}{\frac{n!}{q!\cdot k!\cdot(n-k-q)!}} = \sum\limits_{k=0}^{n-q}{ \frac{(n-q)!}{k!\cdot(n-k-q)!} \frac{n!}{q!\cdot(n-q)!}}$$

$$= \frac{n!}{q!\cdot(n-q)!} \underbrace{ \sum\limits_{k=0}^{n-q}{ \frac{(n-q)!}{k!\cdot(n-k-q)!} } }_{ =2^{n-q} }$$

Comments

Sorry, ich kann nicht ganz folgen. Wo kommen die 1, 2, 3 her? Bzw. wie soll ich danach summieren, ich kenne ja n und q nicht?

Ich hab die Aufgabenstellung zusammengekürzt und vereinfacht, jetzt habe ich:

$\sum\limits_{k=0}^{n-q}{\frac{n!}{q!*k!*(n-k-q)!}}$ = $\frac{2^{n}}{2^{q}}*\frac{n!}{q!*(n-q)!}$

Mein Problem ist dass ich nicht weiß was ich jetzt mit der Summe tun soll...

Danke schonmal

---

Ich ergänze nochmal was zur Antwort.

Apropos 1,2,3 - du kannst auch 4,5,6 oder a,b,c etc. nehmen.

---

Vielen Dank - jetzt hab ichs kapiert!