Sei n ∈N mit n ≥ 1. Zeigen Sie mittels vollständiger Induktion, Kombinatorik

Question

Aufgabe:

Sei n ∈N mit n ≥ 1. Zeigen Sie mittels vollständiger Induktion

\( \sum \limits_{i=2}^{n+1} \left(\begin{array}{cc}i \\ 2 \end{array}\right) = \left(\begin{array}{c}n+2 \\ 3 \\ \end{array}\right) \)

Den Induktionsanfang n=1 hab ich.

Bei Induktionsschritt bin ich mir jetzt nicht sicher, weil in der Vorlesung über dem Summenzeichen immer ein einfaches n stand, dann haben wir im Induktionsschritt m → m+1 gesagt. Ich hab dann erstmal so weitergemacht: Induktionsbehauptung: A(m+1) ist wahr, d.h. zu zeigen:

\( \sum \limits_{i=2}^{(m+1)+1} \begin{pmatrix} i \\ 2 \end{pmatrix} = \begin{pmatrix} (m+1)+2 \\ 3 \end{pmatrix}\)

Induktionsbeweis:

\( \sum \limits_{i=2}^{(m+1)+1} \begin{pmatrix} i \\ 2 \end{pmatrix} = \sum \limits_{i=2}^{m+1} \begin{pmatrix} i \\ 2 \end{pmatrix} + \begin{pmatrix} m+1 \\ 2 \end{pmatrix} \) = (nach Induktionsvoraussetzung)

\( \begin{pmatrix} m+2 \\ 3 \end{pmatrix} + \begin{pmatrix} m+1 \\ 2 \end{pmatrix}\)

An dieser Stelle komme ich nicht mehr weiter.

                                                                                                         

Answer 1

Das liegt daran dass du die Summe falsch aufgeteilt hast. Im rechten binomialkoeffizienten muss ebenfalls m+2 stehen. Dann kannst du rekursionsformel verwenden oder es einfach direkt zeigen.

Gruß

Comments

Ah ok. Danke. Mit der Rekursionsformel komme ich dann auf

\( \begin{pmatrix} m+2 \\ 3 \end{pmatrix} \)

Stimmt dann meine Induktionsbehauptung, in der es heißt:

\( \begin{pmatrix} (m+1)+2 \\ 3 \end{pmatrix} \)?

Oder war die schon falsch? Weil das doch rauskommen sollte.

---

Deine behauptung ist schon korrekt so du solltest aber aus kontinuitätsgründen mit n+1 arbeiten und nicht m+1.

---

Würde ich gerne, finde das auch verwirrend mit m. Darf ich aber leider nicht, das gibt Punktabzug :(

Answer 2

Induktionsanfang: n = 1

Σ (i = 2 bis 2) (i über 2) = (3 über 3)

1 = 1

Induktionsschritt: n --> n + 1

Σ (i = 2 bis (n + 1) + 1) (i über 2) = (((n + 1) + 2) über 3)

Σ (i = 2 bis n + 2) (i über 2) = ((n + 3) über 3)

Σ (i = 2 bis (n + 1) + 1) (i über 2) + ((n + 2) über 2) = ((n + 3) über 3)

((n + 2) über 3) + ((n + 2) über 2) = ((n + 3) über 3)

(n + 2)!/(3!·(n - 1)!) + (n + 2)!/(2!·n!) = (n + 3)!/(3!·n!)

n·(n + 1)·(n + 2)/3! + (n + 1)·(n + 2)/2! = (n + 1)·(n + 2)·(n + 3)/3!

n/3 + 1/1 = (n + 3)/3

n/3 + 1 = n/3 + 1

Comments

Wow, danke! :)

dann wäre meine Lösung ja so richtig schön falsch :(

Bis dahin komme ich ja mit: ((n + 2) über 3) + ((n + 2) über 2) = ((n + 3) über 3)

Danach meinst du so?

\( \frac{(n+2) !}{3 !^{*}(n-1) !}+\frac{(n+2) !}{2 !^{*} n !}=\frac{(n+3) !}{3 !^{*} n !} \)
\( \frac{n^{*}(n+1) *(n+2)}{3 !}+\frac{(n+1) *(n+2)}{2 !}=\frac{(n+1)^{\prime}(n+2) *(n+3)}{3 !} \)
\( \frac{n}{3}+\frac{1}{1}=\frac{n+3}{3} \)
\( \frac{n}{3}+1=\frac{n}{3}+1 \)

Ich denke der Rest steht in irgendwelchen geheimnisvollen Sätzen, die ich nicht verstehe, stimmts? Was mich dabei so verwirrt ist, dass in der Uni immer die Induktionsvoraussetzung als Endergebnis herauskam. Muss das nicht so sein?

---

Ich bin immernoch etwas verwirrt: Sollte am Schluss nicht genau die Formel aus der Induktionsbehauptung stehen, also ∑ (i=2 bis ((m+1)+1)) (i über 2) = (((m+1)+2) über 3) stehen? In den Vorlesungen ist das immer so.

---

Man kann das so machen. Ich zeige meist lieber das die Behauptung auch für n + 1 gilt. d.h. ich setze n + 1 ein und schaue was ich dann damit machen kann um eine Wahre Aussage hinzubekommen.