Binominalkoeffizienten und Induktion

26.10.2007, 12:45

HenryR

Binominalkoeffizienten und Induktion

hallo,
bei mir ist gegeben
Für $\begin{eqnarray*} s=n \end{eqnarray*}$ ergibt dies die Formel $\begin{eqnarray*} \sum_{k=0}^n {n\choose k}=2^n \end{eqnarray*}$ .
jetzt muss ich das beweisen dass das auch für zahlen bis n+1 funzt. aber wie mache ich das? ich kann das leider nicht so schreiben wie mache mit diesen ganzen zeichen, desswegen mache ich das mal so meine idee
(n k) = (n-1 k-1) + (n-1 k)
dann ist doch summe von k=0 bis n (n k-1) + summe k=n+1 bis n+1 (n-1 k)

aber wie mache ich jetzt weiter?
liebe grüße
henry

26.10.2007, 13:09

klarsoweit

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion
Wenn ich das richtig verstehe, willst (sollst) du das mit vollständiger Induktion machen? Wenn ja, hast du den Induktionsanfang gemacht?

Beim Induktionsschritt wird angenommen, daß $\begin{eqnarray*} \sum_{k=0}^n {n\choose k}=2^n \end{eqnarray*}$ für ein beliebiges n gilt, und du mußt zeigen, daß dann auch $\begin{eqnarray*} \sum_{k=0}^{n+1}~{n+1\choose k}=2^{n+1} \end{eqnarray*}$ gilt.

Sind wir uns soweit einig?

26.10.2007, 14:06

HenryR

Auf diesen Beitrag antworten »

ja soweit sind wir uns einig, ich nehme an (getestet mit n=2) dass An gild, jetzt muss ich mit voll.induktion An+1 beweisen

aber wie genau mache ich das?

26.10.2007, 14:27

klarsoweit

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion
Also das ist die Aussage A(n+1):

$\begin{eqnarray*} \sum_{k=0}^{n+1}~{n+1\choose k}=2^{n+1} \end{eqnarray*}$

Jetzt nehmen wir uns die linke Seite her und formen die solange um, bis wir die rechte Seite erhalten. Also los gehts:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~{n+1\choose k} = \sum_{k=0}^{0}~{n+1\choose k} + \sum_{k=1}^{n}~{n+1\choose k} + \sum_{k=n+1}^{n+1}~{n+1\choose k} \end{eqnarray*}$

Der erste und letzte Summand sind jeweils 1. Beim mittleren Summanden kannst du die Beziehung $\begin{eqnarray*} {n+1\choose k} = {n\choose k-1} + {n \choose k} \end{eqnarray*}$ anwenden. Kommst du nun weiter?

26.10.2007, 16:22

Mariana

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion
Eine kurze Zwischenfrage habe ich wenn ich fragen darf, da ich nicht der Threadsteller bin.
@Klarsoweit: Wie kommst du denn auf die Beziehung $\begin{eqnarray*} \begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix} n \\ k-1 \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$
Danke und liebe Grüße: Mariana Blumen

26.10.2007, 21:54

HenryR

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion

Zitat:

Original von Mariana

@Klarsoweit: Wie kommst du denn auf die Beziehung $\begin{eqnarray*} \begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix} n \\ k-1 \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$

weil die allgemeine umfprmung die ist:

$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ k \end{pmatrix} \end{eqnarray*}$
wenn du dann da n+1 einsetzt hast du nur noch ns ^^

@klarsoweit, vielen lieben dank schonmal, ich schaue mir das gleich an und dann sage ich bescheid Big Laugh

26.10.2007, 22:01

HenryR

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion

Zitat:

Der erste und letzte Summand sind jeweils 1. Beim mittleren Summanden kannst du die Beziehung $\begin{eqnarray*} {n+1\choose k} = {n\choose k-1} + {n \choose k} \end{eqnarray*}$ anwenden. Kommst du nun weiter?

aber was ist denn bitte (n k-1) ? ich raffe net was ich mit der -1 machen soll, das ist mein problem... *schnief*

26.10.2007, 23:00

HenryR

Auf diesen Beitrag antworten »

außerdem gilt doch $\begin{eqnarray*} s=n \end{eqnarray*}$ ergibt dies die Formel $\begin{eqnarray*} \sum_{k=0}^n {n\choose k}=2^n \end{eqnarray*}$ nur wenn k=0, für k=1 geht das nicht, also darf ich die summer die du gemacht hast doch gatso machen, also die erste von deinen dreien, da ich dann in der zweiten k=1 habe. wenn ich dann die andere umformung für (n k) einsetze die du da geschrieben hast, darf ich das nicht mehr iensetzen $\begin{eqnarray*} s=n \end{eqnarray*}$ ergibt dies die Formel $\begin{eqnarray*} \sum_{k=0}^n {n\choose k}=2^n \end{eqnarray*}$ da das dann nicht mehr stimmt oder?

lg
henry

26.10.2007, 23:40

Dunkit

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion

Zitat:

Original von Mariana
Eine kurze Zwischenfrage habe ich wenn ich fragen darf, da ich nicht der Threadsteller bin.
@Klarsoweit: Wie kommst du denn auf die Beziehung $\begin{eqnarray*} \begin{pmatrix} n+1 \\ k \end{pmatrix} = \begin{pmatrix} n \\ k-1 \end{pmatrix} + \begin{pmatrix} n \\ k \end{pmatrix} \end{eqnarray*}$
Danke und liebe Grüße: Mariana Blumen

ICh beantworte das einfach mal: Das ist die Rekursionsformel, nachzulesen in manchen Formelsammlungen und bei Aufgaben mit Binominalkoeffizienten immer sehr nützlich

27.10.2007, 09:24

klarsoweit

Auf diesen Beitrag antworten »

RE: Binominalkoeffizienten und Induktion
@HenryR: was meinst du mit diesem "s = n" ? verwirrt

Ich sehe kein s, also stört es mich nicht.

Ich rechne noch den nächsten Schritt vor:

$\begin{eqnarray*} \sum_{k=0}^{n+1}~{n+1\choose k} = \sum_{k=0}^{0}~{n+1\choose k} + \sum_{k=1}^{n}~{n+1\choose k} + \sum_{k=n+1}^{n+1}~{n+1\choose k} \end{eqnarray*}$

$\begin{eqnarray*} = 1 + \sum_{k=1}^{n}~\left({n\choose k-1} + {n \choose k}\right) + 1 = 1 + \sum_{k=1}^{n}~{n\choose k-1} + \sum_{k=1}^n~{n \choose k} + 1 \end{eqnarray*}$

Substituiere in der 1. Summe den Laufindex k durch k = j+1. Passe die Summengrenzen entsprechend an. Die 2. Summe kannst du bei k=0 beginnen und dafür die letzte "+ 1" streichen.

27.10.2007, 12:49

HenryR

Auf diesen Beitrag antworten »

ach so und bei der ersten summe kann ich dann auch 2hoch n einsetzen, weil ich ja k=1 habe oder was? weil mein borb ist ja ich weiß nicht was ich mit der summe von (n k-1) machen soll. geht das denn? ich habe das mal aufgeschrieben, aber dann ahbe ich ja ne eins zu viel, was mache ich mit der?

dieses s=n ist nur weil ich was anderes zitiert habe ^^

27.10.2007, 14:39

klarsoweit

Auf diesen Beitrag antworten »

Zitat:

Original von HenryR
weil mein borb ist ja ich weiß nicht was ich mit der summe von (n k-1) machen soll. geht das denn?

Ich hatte doch schon gesagt, daß du den Laufindex k mittels k=j+1 substituieren sollst:

$\begin{eqnarray*} \sum_{k=1}^{n}~{n\choose k-1} = \sum_{j=?}^{?}~{n\choose j+1-1} \end{eqnarray*}$

Jetzt mußt du nur überlegen, zwischen welchen Grenzen sich der neue Laufindex j bewegt.

Neue Frage »

Antworten »

Binominalkoeffizienten und Induktion

Verwandte Themen