Binomialkoeffizient. Zeigen, dass ∑ (k=0 bis n) ((2n+1) über k)=2^2n

Question

  wie kann ich folgende Summe umschreiben?

Ich soll per Induktion zeigen ∑ (k=0 bis n) ((2n+1) über k)=2²ⁿ

Ich habe schon den Induktionsanfang gemacht und bin jetzt beim Induktionsschritt.

∑ (k=0 bis n+1) ((2(n+1)+1)über k)= ∑ (k=0 bis n) (2n+1 über k) +((2(n+1)+1) über k)

Ich weiß, dass ∑ (k=0 bis n) (2n+1 über k)=2²ⁿ ist. Allerdings weiß ich jetzt nicht mehr weiter.

Comments

EDIT: Achtung du hattest ein n zu viel in der Überschrift. Es heisst Binomialkoeffizient. Habe das korrigiert.

Answer 1

An dem Startausdruck \(\sum_{k=0}^{n+1}{2n+3\choose k}\) für den Induktionsschritt stoert irgendwie die \(2n+3\) im Binomialkoeffizienten oben, oder? Baue das mit dem Bildungsgesetz der Binomialkoeffizienten in zwei Schritten zurueck, so dass da nur noch Binomialkoeffizienten mit \(2n+1\) oben stehen.

Comments

Summiere die ganze Zeile durch, das ergibt 2^{2n+1}, nutze die Symmetrie : die halbe Zeile hat die halbe Summe.

---

Kommt jetzt drauf an, ob es zwingend eine Induktion werden soll, oder ob ein direkter Beweis auch geht. "Ich soll per Induktion zeigen" steht in der Frage.

---

Ich muss das schon mit Induktion machen. Wie macht man das dann?

---

Ein Weg ist in der Antwort skizziert. Wenn Dir nichts Besseres einfaellt, kannst Du ihn beschreiten.

---

Ja ich habe verstanden dass ich das ganze irgendwie auf die Form 2n+1 bringen muss. Nur weiß ich diese Umformung nicht. Dafür benutze ich doch folgende Formel oder?
(n über k)+(n über (k+1)=((n+1)über (k+1)). Aber ich weiß leider nicht weiter

---

Und von was ist -- nach eben gerade dieser Formel -- \(2n+3\choose k\) die Summe?

---

von ((2n+2) über k)+((2n+2) über (k-1))?

---

Ja. Und jetzt halt noch mal.

---

Okay das habe ich nun versucht. Ich erhalte dann insgesamt:

∑(von k=0 bis n) (((2n+1)über k)+((2n+1)über (k-1)))+ Summe (k=0 bis n) (((2n+1) über (k-1))+((2n+1)über (k-2)))+((2n+3) über (n+1)).

Das habe ich nun vereinfacht zu

2²ⁿ+2∑(k=0 bis n) ((2n+1) über (k-1)) + ∑ (k=0 bis n) ((2n+1) über (k-2))+ ((2n+3) über (n+1))

Stimmt das dann so? Weil wenn ich das weiter vereinfache komme ich nicht auf das richtige Ergebnis. Irgendwo muss ein Fehler sein

---

k geht von 0 bis n+1. Und dann musst Du eben eine Indexverschiebung machen, so dass in den Binomialkoeffizienten unten immer k steht. Mit Induktionsvoraussetzung kommt für die Summen zweimal 4ⁿ raus, einmal 4ⁿ - etwas, und einmal 4ⁿ + etwas. Insgesamt 4 · 4ⁿ = 4ⁿ⁺¹ wie gewuenscht.