Binomialkoeffizient n über k. Warum immer ganzzahlig?

Question

Wie kann man es beweisen, warum n über k immer ganzzahlig ist ?

Danke

Comments

Vom Duplikat:

Titel: Vollständige Induktion mit Binomialkoeffizienten

Stichworte: binomialkoeffizient,induktion,vollständige-induktion,summenformel,analysis

Nabend ich brauche Hilfe bei dieser Aufgabe

Aus der Definition des Binomialkoeffizienten ( n über k) = n!/k!(n-k) ist es nicht klar, dass hier immer natürliche Zahlen herauskommen. Beweisen sie mit vollständiger Induktion, dass (n über k) ∈N0 für alle n ∈N0 und k ∈Z.

Vielen Dank

---

das wurde hier bereits beantwortet.

Answer 1

 
du müsstest die Rekursion \(\displaystyle\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}\) zeigen.

Das könntest du mithilfe der vollständigen Induktion nach n tun, mit

Induktionsvoraussetzung: \(\displaystyle\binom{n}{k}\)
Induktionsbehauptung: \(\displaystyle\binom{n+1}{k}\)

Answer 2

das lässt sich per vollständiger Induktion beweisen. Zeige, dass $${ 1 \choose 0}, \space {1 \choose 1} \space \in \mathbb{N}$$sind. Weiter ist immer $${ n\choose 0} = { n\choose n} =1$$Und wenn Du nun zeigen kannst, dass $${ n+1 \choose k } = { n \choose k-1 } + { n \choose k } \quad 0 \lt k \lt n$$gilt, dann hast Du bewiesen, dass \({ n+1 \choose k }\) bzw. \({ n \choose k }\) stets eine Summe zweier ganzen Zahlen ist und somit selbst ganzzahlig.

Kommst Du mit dem Induktionsschritt klar? Sonst melde Dich noch mal.

Gruß Werner

Comments

Den Induktionsschritt habe ich durchgeführt; mir ist aber dennoch nicht klar, wie ich beweisen kann, ...

daß, wenn n über k ganzzahlig ist, auch n+a über k+b ganzzahlig ist

Answer 3

Induktionsvoraussetzung: (nk)∈ℕ für alle k mit 0≤k≤n

Induktionsbehauptung: (n+1k)∈ℕ für alle k mit 0≤k≤n+1

Im Induktionsschritt n→n+1 kannst du nun zumindest für 1≤k≤n die genannte Rekursionsformel (n+1k)=(nk−1)+(nk) anwenden. Und dann sind beide (!!!) Summanden gemäß Induktionsvoraussetzung ganzzahlig.

Die "Randfälle" k=0 und k=n+1 musst du noch extra betrachten, dann ist die Sache vollständig gegessen.

Hoffe ich konnte dir helfen!