Mengenbeweis (Kombinatorik)

Question

wie geht man folgende Aufgaben an? Habe bei der a) bereits versucht die rechte Seite auszumultiplizieren, aber bekomme da keine vernünftige Lösung raus und wüsste nicht, wie ich dies mit Hilfe der binomischen Formeln schreiben soll. Bei der b) weiß ich auch nicht, wie ich das zeigen soll.

Seien $$m, n\in \mathbb{N}0$$

Gruß

Answer 1

binomischer Satz (Formel)

$$(x+y)^n =\sum_{i=0}^{n}\begin{pmatrix} n\\k \end{pmatrix}{x^{n-k}y^{k}}$$

Hier also

$$(1+x)^{n+m} =\sum_{k=0}^{n+m}\begin{pmatrix} n+m\\k \end{pmatrix}{x^{k}}$$

und

$$(1+x)^{n} =\sum_{i=0}^{n}\begin{pmatrix} n\\i \end{pmatrix}{x^{i}}$$

und

$$(1+x)^{m} =\sum_{j=0}^{m}\begin{pmatrix} m\\j \end{pmatrix}{x^{j}}$$

Dann wird aus der gegebenen Gleichung

$$(1+x)^{n+m} =\sum_{k=0}^{n+m}\begin{pmatrix} n+m\\k \end{pmatrix}{x^{k}} = \sum_{i=0}^{n}\begin{pmatrix} n\\i \end{pmatrix}{x^{i}} *\sum_{j=0}^{m}\begin{pmatrix} m\\j \end{pmatrix}{x^{j}}$$

und da die Summanden der ersten Summe nicht von j abhängen, kann man sie in die 2. Summe ziehen:

$$= \sum_{i=0}^{n}\sum_{j=0}^{m}\begin{pmatrix} n\\i \end{pmatrix}{x^{i}} *\begin{pmatrix} m\\j \end{pmatrix}{x^{j}}$$

$$= \sum_{i=0}^{n}\sum_{j=0}^{m}\begin{pmatrix} n\\i \end{pmatrix}\begin{pmatrix} m\\j \end{pmatrix}{x^{i+j}}$$

Und jetzt wird das alles nach den Potenzen von x geordnet. Dann hat man

$$= \sum_{k=0}^{n+m}\sum_{i=0}^{k}\begin{pmatrix} n\\i \end{pmatrix}\begin{pmatrix} m\\k-i \end{pmatrix}{x^{k}}$$

$$= \sum_{k=0}^{n+m} (\sum_{i=0}^{k}\begin{pmatrix} n\\i \end{pmatrix}\begin{pmatrix} m\\k-i \end{pmatrix}){x^{k}}$$

und wenn du jetztnoch aus dem i ein kleines L machst, passt es genau.

Comments

Stimmt, das mit dem Lehrsatz hatte ich auch dann vermutet. Danke sehr!