TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 183

Man zeige

$\sum _{k=0}^n(-1{)}^k\left(\begin{array}{c}x\\ k\end{array}\right)=(-1{)}^n\left(\begin{array}{c}x-1\\ n\end{array}\right)$

für alle $x\ge 1$ und $x\in \mathbb{N}$ mit Hilfe der Identität $(1+z{)}^x\cdot \frac{1}{1+z}=(1+z{)}^{x-1}$.

Anm.: Fehler in der Angabe, es müßte heißen: "...und $n\in \mathbb{N}$..."

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag (1)

Ein motivierter Kollege hat dieses Beispiel als Induktion über $n$ vorgerechnet, ohne auf die o.g. Identität zurückgreifen zu müssen (Induktion über $x$ wäre angeblich auch möglich! Mathematiker vor!).

Lt. UE-Leiter ist das akzeptabel, auch weil das zugrundeliegenden Zeugs heuer in der VO nicht erschöpfend behandelt wurde, und daher keine UE-Gruppe das Beispiel angabengemäß lösen konnte ;-)

Weitere Lösungsvorschläge daher: sehr erwünscht!!

$\sum _{k=0}^n(-1{)}^k\left(\begin{array}{c}x\\ k\end{array}\right)=(-1{)}^n\left(\begin{array}{c}x-1\\ n\end{array}\right),x\ge 1,n\in \mathbb{N}$

Induktion über $n$:

$n=0:$

$\underset{1}{\underbrace{(-1{)}^0}}\underset{1}{\underbrace{(\genfrac{}{}{0ex}{}{x}{0})}}=\underset{1}{\underbrace{(-1{)}^0}}\underset{1}{\underbrace{(\genfrac{}{}{0ex}{}{x-1}{0})}}\surd (\mathrm{\forall }m:m^0:=1,(\genfrac{}{}{0ex}{}{m}{0}):=1)$

$n\to n+1:$

$(-1{)}^k(\genfrac{}{}{0ex}{}{x}{n})+(-1{)}^{n+1}(\genfrac{}{}{0ex}{}{x}{n+1})\stackrel{?}{=}(-1{)}^{n+1}(\genfrac{}{}{0ex}{}{x-1}{n+1}),$ Ansatz soweit klar? :) Jetzt wird's nämlich ungemütlich..:

$(-1{)}^n\frac{(n-1)!}{n!(x-1-n)!}+(-1{)}^{n+1}\frac{x!}{(n+1)!(x-n-1)!}\stackrel{?}{=}(-1{)}^{n+1}\frac{(x-1)!}{(n+1)!\underbrace{(x-1-n-1)!}}$

Nebenrechnung: $(x-1-n-1)!=\frac{(x-1-n)!}{(x-1-n)}$, weil ja
$m!=(m-1)!\cdot m\Rightarrow$
$\Rightarrow (x-n-2)!=\frac{(x-n-1)!}{(x-n-1)}$

$(-1{)}^n\frac{(n-1)!}{n!(x-1-n)!}+(-1{)}^{n+1}\frac{x!}{(n+1)!(x-n-1)!}\stackrel{?}{=}(-1{)}^{n+1}\frac{(x-1)!(x-n-1)}{(n+1)!(x-n-1)}$

Gleicher Nenner, auf die andere Seite des Gleichheizzeichens verschieben:

$(-1{)}^n(x-1)!+(-1{)}^{n+1}\frac{x!}{n+1}-(-1{)}^{n+1}\frac{(x+1)!(x-1-n)}{n+1}\stackrel{?}{=}0$

$(-1{)}^n(x-1)!+(-1{)}^{n+1}\left(\frac{x!-(x-1)!(x-n-1)}{n+1}\right)\stackrel{?}{=}0$

$\underset{\pm 1}{\underbrace{(-1{)}^n}}+\underset{\mp 1}{\underbrace{(-1{)}^{n+1}}}\underset{1}{\underbrace{\left(\frac{x-(x-n-1)}{n+1}\right)}}\stackrel{?}{=}0$

$\pm 1+\mp 1=0$ QED.

Na, wenn das kein Beispiel für mathematische Hirnwixerei ist... T'schuldigung :)

Ich ersuche darum, Tipp- und andere Fehler zu beseitigen.

---

g, Baccus 22:41, 1. Dez 2006 (CET)