Vollständige Induktion

29.10.2015, 20:01

arni19102

Vollständige Induktion

Meine Frage:
Fage im Bild.

Meine Ideen:
Ich habe das mit Vollständiger Induktion probiert.
Anfang hab ich schon .Jetzt geht es um den Schritt.
Ich muss Zeigen n-->n+1
Nur weis ich nicht genau wie der schritt geht und ob ich dass n mit n+1 ersetzen muss im binomialkoeffizienten? Wenn ja geht das dann mit der Rekursionsformel (2n+1 über 2k)=(2n über 2k-1)+(2n über 2k-1)?

oder gibt es einer einfachere Variante zb Binomischer lehrsatz?

29.10.2015, 20:39

HAL 9000

Auf diesen Beitrag antworten »

RE: Vollständige Induktion

Zitat:

Original von arni19102
oder gibt es einer einfachere Variante zb Binomischer lehrsatz?

Das wäre meine Empfehlung, und zwar via $\begin{align*} (1+1)^{2n} + (1-1)^{2n} = 2^{2n} \end{align*}$ .

29.10.2015, 21:37

arni19102

Auf diesen Beitrag antworten »

Okay ich komme jz soweit: $\begin{eqnarray*} (1+1)^{2n} =\sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} *1^k*1^{2n-k} \end{eqnarray*}$ = $\begin{eqnarray*} 2^{2n} =\sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} \end{eqnarray*}$

und für $\begin{eqnarray*} (1-1)^{2n} =\sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix} *1^k*(-1)^{2n-k} \end{eqnarray*}$ = $\begin{eqnarray*} 2^{2n} =\sum\limits_{k=0}^{2n} \begin{pmatrix} 2n \\ k \end{pmatrix}*(-1)^{-k} \end{eqnarray*}$

wie komm ich da dann weiter muss ich die Summe aufspalten und sagen das sind 2 summen die jeweils die Grenzen k=0 und n haben ( weil 2n=n+n)?

29.10.2015, 21:53

HAL 9000

Auf diesen Beitrag antworten »

Zunächst mal ist der Wert der zweiten Summe nicht $\begin{align*} 2^{2n} \end{align*}$ , sondern $\begin{align*} 0^{2n}=0 \end{align*}$ .

Und zum anderen hatte ich dir ja bereits empfohlen, beide Summen zu addieren, das ergibt dann

$\begin{align*} 2^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} \left( 1 + (-1)^k \right) \end{align*}$

Und jetzt schau dir an, was in der Summe für gerade sowie für ungerade $\begin{align*} k \end{align*}$ passiert, insbesondere mit dem Term $\begin{align*} \left( 1 + (-1)^k \right) \end{align*}$ .

29.10.2015, 22:12

arni19102

Auf diesen Beitrag antworten »

Ok ja das war mir klar das die 2te summe 0 ist , ich hab mich verschrieben^^
Bis zu dieser Summe kann ich es nachvollziehen. wenn k gerade ist hat man (1+1) also 2.
und wenn k ungerade ist (1-1)=0. Somit fällt genau die Hälfte der Summe weg 1/2=2^(-1).

29.10.2015, 22:25

HAL 9000

Auf diesen Beitrag antworten »

Genau, wir können also die ungeraden Indizes $\begin{align*} k=2j-1 \end{align*}$ weglassen und lassen nur noch die geraden Indizes $\begin{align*} k=2j \end{align*}$ drin:

$\begin{align*} 2^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} \left( 1 + (-1)^k \right) = \sum_{j=0}^n \binom{2n}{2j} \cdot 2 \end{align*}$

Von hier zur (ersten) Behauptung ist es ja nun wirklich nicht mehr weit. Augenzwinkern

29.10.2015, 22:37

arni19102

Auf diesen Beitrag antworten »

ok kann ich gut nachvollziehen Augenzwinkern

also 2 ist konstanter Fakto den man nun vor die Summe Schreiben darf .Nun dividiert man diesen und erhält auf der anderen Seite *1/2 und das ist dann 2^(-1) sodass steht $\begin{eqnarray*} \sum\limits_{k=1}^{n} \begin{pmatrix} 2n \\ 2k \\ \end{pmatrix} =2^{2n} *\frac{1}{2} = 2^{2n-1} \end{eqnarray*}$

so sollte das dann auschaun würde ich sagen ?
mir war nur schleierhaft wie die obere Grenze $\begin{eqnarray*} 2^n \end{eqnarray*}$ einfach auf n umgeändert wird. Versteh ich nun so dass die Grenzen 0-n genau die Hälfte der Summe darstellen und $\begin{eqnarray*} 2j \end{eqnarray*}$
definiert mir das dann genau die elemente bleiben sollen die gerade sind. sonst wären es nämlich nur die elemente der ersten hälfte der Summe und davon würden dann wieder nur die hälfte bleiben also 1/4.

ich glaube ich habs verstanden , Danke Augenzwinkern

29.10.2015, 22:41

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von arni19102
mir war nur schleierhaft wie die obere Grenze $\begin{eqnarray*} 2^n \end{eqnarray*}$ einfach auf n umgeändert wird.

In der Originalsumme summierst du $\begin{align*} k \end{align*}$ mit $\begin{align*} 0\leq k\leq 2n \end{align*}$ . Jetzt betrachtest du nur Indizes $\begin{align*} k=2j \end{align*}$ , für die dann immer noch $\begin{align*} 0\leq 2j\leq 2n \end{align*}$ gelten muss, also umgeformt $\begin{align*} 0\leq j\leq n \end{align*}$ .

Alles keine Zauberei oder nötige Sonder- oder Merkregeln, sondern ganz normale sorgfältige Betrachtungen. Augenzwinkern

Genauso geht es, wenn wir die ungeraden Indizes $\begin{align*} k=2j-1 \end{align*}$ in diesem Bereich betrachten, für die muss genauso $\begin{align*} 0\leq 2j-1\leq 2n \end{align*}$ gelten, umgestellt $\begin{align*} \frac{1}{2}\leq j\leq n+\frac{1}{2} \end{align*}$ . Da aber $\begin{align*} j \end{align*}$ nur ganze Zahlen annimmt, ist letztere Doppelungleichung gleichbedeutend mit $\begin{align*} 1\leq j\leq n \end{align*}$ .

Insbesondere bedeutet diese Zerlegung in gerade und ungerade $\begin{align*} k \end{align*}$ auch für die Gesamtsumme

$\begin{align*} \sum_{k=0}^{2n} \binom{2n}{k} = \sum_{j=0}^n \binom{2n}{2j} ~+~ \sum_{j=1}^n \binom{2n}{2j-1} \end{align*}$ ,

womit du dann die zweite Behauptung aus der ersten folgern kannst.

29.10.2015, 23:09

arni19102

Auf diesen Beitrag antworten »

Okay ja das klingt alles dann nicht so übel smile

Eine Frage hätte ich noch da ich in zukunft oft solche beispiele Rechnen werde . Wie kommt man zu dieser Idee bzw dem Ansatz den du mir zur Verfügung gestellt hast.? Hast du da vl eventuell ein paar tipps für mich?

29.10.2015, 23:28

HAL 9000

Auf diesen Beitrag antworten »

Ich bin der Richtige für "Warum gilt"-Fragen. Für "Wie kommt man drauf"-Fragen hatte ich noch nie was übrig. Augenzwinkern

Neue Frage »

Antworten »

Vollständige Induktion

Verwandte Themen