Binomialkoeffizient < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie die folgende Identität mit einer geeigneten Beweismethode:
[mm] \summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=2^n [/mm] |
Hallo!
Ich komme bei dieser Aufgabe leider nicht weiter.
Ich habe es zunächst mit direktem Umformen probiert und bin nun bei Induktion angelangt, komme aber auch hier nun nicht weiter:
ich möchte zeigen, dass gilt: [mm] \summe_{k=0}^{n+1}\bruch{1}{2^k}\vektor{n+k+1 \\ k}=2^{n+1} [/mm] unter der Annahme, dass [mm] \summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=2^n [/mm] gilt.
[mm] \summe_{k=0}^{n+1}\bruch{1}{2^k}\vektor{n+k+1 \\ k}
[/mm]
[mm] =\bruch{1}{2^{n+1}}\vektor{2(n+1) \\ (n+1)}+\underbrace{\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}}_{=2^n}+\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k-1}
[/mm]
[mm] =2^n +\bruch{1}{2^{n+1}}\vektor{2(n+1) \\ (n+1)}+\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k-1}
[/mm]
[mm] =2^n+ \bruch{1}{2^n}\vektor{2n-1 \\ n}+\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k-1}
[/mm]
mit: [mm] \vektor{2n \\ n}=2\vektor{2n-1 \\ n-1}
[/mm]
Bringt mich dieser Ansatz überhaupt weiter oder sollte ich eine andere Beweismethode nehmen?
Ich wäre für Hilfe echt dankbar!
VG
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:14 Do 18.12.2014 | | Autor: | Marcel |
Hallo,
> Zeigen Sie die folgende Identität mit einer geeigneten
> Beweismethode:
> [mm]\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=2^n[/mm]
>
> Hallo!
>
> Ich komme bei dieser Aufgabe leider nicht weiter.
> Ich habe es zunächst mit direktem Umformen probiert und
> bin nun bei Induktion angelangt, komme aber auch hier nun
> nicht weiter:
ich kann nicht versprechen, dass es wirklich hilft. Aber das
${n+k [mm] \choose [/mm] k}$
erinnert mich ein wenig
hieran.
(Wobei das natürlich eher zu [mm] ${n+\ell \choose k}$ [/mm] passt, was im Link steht, wobei
[mm] $\ell$ [/mm] fest!)
Was mir als erstes in den Sinn käme: Es ist ja
[mm] $2^n=\sum_{k=0}^n [/mm] {n [mm] \choose k}\,.$
[/mm]
Daher ist die zu beweisende Aussage gleichwertig mit
[mm] $\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=\sum_{k=0}^n [/mm] {n [mm] \choose [/mm] k}$
[mm] $\iff$ $\sum_{k=0}^n \left\{\bruch{1}{2^k}\vektor{n+k \\ k}-{n \choose k}\right\}=0\,.$
[/mm]
Ob das hilft, weiß ich nicht. Aber Du kannst es ja mal probieren. Wenn nicht:
Dann ist es halt so. In der Mathematik muss man einfach manchmal die
ein oder andere Idee einfach beginnen, um zu sehen, ob sie zum Ziel
führt oder nicht.
Gruß,
Marcel
|
|
|
| |
|
Hallo!
Vielen Dank für den Tipp erstmal, doch leider bin ich immer noch nicht weiter...
> Was mir als erstes in den Sinn käme: Es ist ja
>
> [mm]2^n=\sum_{k=0}^n {n \choose k}\,.[/mm]
>
> Daher ist die zu beweisende Aussage gleichwertig mit
>
> [mm]\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=\sum_{k=0}^n {n \choose k}[/mm]
>
> [mm]\iff[/mm] [mm]\sum_{k=0}^n \left\{\bruch{1}{2^k}\vektor{n+k \\ k}-{n \choose k}\right\}=0\,.[/mm]
Damit komme ich leider auch nicht weiter, vor allem, da die einzelnen Summanden [mm] \bruch{1}{2^k}\vektor{n+k \\ k} [/mm] und [mm] \vektor{n \\ k} [/mm] nicht immer für alle k gleich sind.
Hat vllt noch jemand eine Idee?
Ich bin inzwischen echt ratlos...
Vielen Dank!
VG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:49 Fr 19.12.2014 | | Autor: | Marcel |
Hallo,
> Hallo!
>
> Vielen Dank für den Tipp erstmal, doch leider bin ich
> immer noch nicht weiter...
>
> > Was mir als erstes in den Sinn käme: Es ist ja
> >
> > [mm]2^n=\sum_{k=0}^n {n \choose k}\,.[/mm]
> >
> > Daher ist die zu beweisende Aussage gleichwertig mit
> >
> > [mm]\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=\sum_{k=0}^n {n \choose k}[/mm]
>
> >
> > [mm]\iff[/mm] [mm]\sum_{k=0}^n \left\{\bruch{1}{2^k}\vektor{n+k \\ k}-{n \choose k}\right\}=0\,.[/mm]
>
> Damit komme ich leider auch nicht weiter, vor allem, da die
> einzelnen Summanden [mm]\bruch{1}{2^k}\vektor{n+k \\ k}[/mm] und
> [mm]\vektor{n \\ k}[/mm] nicht immer für alle k gleich sind.
>
>
>
> Hat vllt noch jemand eine Idee?
> Ich bin inzwischen echt ratlos...
wenn ich dazu komme, schaue ich mir Deinen Induktionsbeweis nochmal
genauer an. Eigentlich sollte ein Induktionsbeweis möglich sein.
Ansonsten kann man höchstens mal gucken, ob man sowas wie das
Produkt zweier (endlicher) Reihen hier irgendwo sieht. Meist sieht man
aber auch nur das, was man schon kennt.
Daher: Vor Sonntag wird's bei mir eher nichts...
Ich schicke aber mal den Link an jemanden, der, selbst, wenn er gerade
keine Zeit hat, vielleicht weißt, wo Du suchen kannst. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:20 So 21.12.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
Hallo!
Ich hab das jetzt nochmal ein bisschen umgeformt, bin mir da aber sehr unsicher bei meinem ersten Umformungsschritt!
Darf ich die Summe da einfach herausziehen?
Es gilt: [mm] 2^n=\summe_{k=0}^{n}\vektor{n \\ k}
[/mm]
[mm] \summe_{k=0}^{n+k} \bruch{1}{\summe_{i=0}^{k}\vektor{k \\ i}} \vektor{n+k \\ k}=\summe_{k=0}^{n}\vektor{n \\ k}
[/mm]
[mm] \gdw\bruch{\summe_{k=0}^{n+k} \vektor{n+k \\ k}}{\summe_{i=0}^{k}\vektor{k \\ i}} [/mm] = [mm] \summe_{k=0}^{n}\vektor{n \\ k}
[/mm]
[mm] \gdw\summe_{k=0}^{n+k} \vektor{n+k \\ k}=\summe_{k=0}^{n}\vektor{n \\ k} [/mm] * [mm] \summe_{i=0}^{k}\vektor{k \\ i}
[/mm]
[mm] \gdw\summe_{k=0}^{n+k} \vektor{n+k \\ k} [/mm] = [mm] 2^n [/mm] * [mm] 2^k
[/mm]
[mm] \gdw\summe_{k=0}^{n+k} \vektor{n+k \\ k} [/mm] = [mm] 2^{n+k}
[/mm]
Vielen Dank!!
VG
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:48 So 21.12.2014 | | Autor: | Marcel |
Hallo,
> Hallo!
>
> Ich hab das jetzt nochmal ein bisschen umgeformt, bin mir
> da aber sehr unsicher bei meinem ersten Umformungsschritt!
> Darf ich die Summe da einfach herausziehen?
>
>
> Es gilt: [mm]2^n=\summe_{k=0}^{n}\vektor{n \\ k}[/mm]
>
> [mm]\summe_{k=0}^{n+k} \bruch{1}{\summe_{i=0}^{k}\vektor{k \\ i}} \vektor{n+k \\ k}=\summe_{k=0}^{n}\vektor{n \\ k}[/mm]
>
> [mm]\gdw\bruch{\summe_{k=0}^{n+k} \vektor{n+k \\ k}}{\summe_{i=0}^{k}\vektor{k \\ i}}[/mm] = [mm]\summe_{k=0}^{n}\vektor{n \\ k}[/mm]
Dieser Schritt funktioniert so nicht! Im Nenner steht ja eigentlich [mm] $2^k\,,$ [/mm] was
von dem k, dem Laufindex der Summe, die nun im Zähler alleine steht,
abhängt. I.A. kannst Du ja auch nicht
[mm] $\sum_{k=1}^n a_k b_k=(\sum_{k=1}^n a_k)*\sum_{k=1}^n b_k$
[/mm]
schreiben!
> [mm]\gdw\summe_{k=0}^{n+k} \vektor{n+k \\ k}=\summe_{k=0}^{n}\vektor{n \\ k}[/mm] * [mm]\summe_{i=0}^{k}\vektor{k \\ i}[/mm]
>
> [mm]\gdw\summe_{k=0}^{n+k} \vektor{n+k \\ k}[/mm] = [mm]2^n[/mm] * [mm]2^k[/mm]
>
> [mm]\gdw\summe_{k=0}^{n+k} \vektor{n+k \\ k}[/mm] = [mm]2^{n+k}[/mm]
Also wenn die Aufgabenstellung falsch ist, und nur
[mm] $2^{n}=\sum_{\red{m}=0}^{n+k} \frac{1}{2^k}{n+k \choose \red{m}}$
[/mm]
zu zeigen ist:
Das können wir nun sehr kurz machen: Für jedes $N [mm] \in \IN_0$ [/mm] ist
[mm] $2^{N}=\sum_{k=0}^N [/mm] {N [mm] \choose k}\,.$
[/mm]
Also folgt
[mm] $2^{n+k}=\sum_{m=0}^{n+k}{n+k \choose m}$
[/mm]
[mm] $\Longrightarrow$ $2^n=\sum_{m=0}^{n+k} \frac{1}{2^k}*{n+k \choose \red{m}}$
[/mm]
Das ist aber nicht das, was Du zeigen solltest - oder hast Du Dich da bei
der Aufgabenstellung verschrieben?
P.S. Hast Du die Formel mal für $n=0,1,2,3$ geprüft?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:03 So 21.12.2014 | | Autor: | Marcel |
Hallo,
> Zeigen Sie die folgende Identität mit einer geeigneten
> Beweismethode:
> [mm]\summe_{k=0}^{n}\bruch{1}{2^k}\vektor{n+k \\ k}=2^n[/mm]
so ist die Aufgabe nicht lösbar, es sollte dort etwa
[mm] $\sum_{\red{m}=0}^n \frac{1}{2^k} [/mm] {n+k [mm] \choose \red{m}}$
[/mm]
stehen.
Zur Kontrolle ein Matlab/Octave Code:
| 1: | clear all; close all;
| | 2: | for n = 0 : 4
| | 3: | S = 0;
| | 4: | for k = 0 : n
| | 5: | S = S + 1/2^k*nchoosek(n+k,k);
| | 6: | end;
| | 7: | disp(['Ausgabe S fuer n = ',num2str(n),' ist S = ', ...
| | 8: | num2str(S)]);
| | 9: | disp(['Vergleich mit 2^n: ',num2str(2^n)]);
| | 10: | fprintf('\n\nWeiter geht's!\n\n');
| | 11: | pause(1)
| | 12: | end; |
(Der Code passt zur Original-Aufgabenstellung!)
Da bekomme ich die Ausgaben:
Ausgabe S fuer n = 0 ist S = 1
Vergleich mit [mm] 2^n: [/mm] 1
Weiter geht's!
Ausgabe S fuer n = 1 ist S = 1.5
Vergleich mit [mm] 2^n: [/mm] 2
Rechne es auch mal von Hand nach!
[mm] $2^1=2\,,$ [/mm] aber
[mm] $\sum_{k=0}^1 \frac{1}{2^k} [/mm] *{1 [mm] \choose k}=\frac{1}{2^0}*{1 \choose 0}+\frac{1}{2^1}*{1 \choose 1}=1+\frac{1}{2}=1.5\,$
[/mm]
Edit: Sorry, das war Quatsch. Nach der Fehlerkorrektur im Programmierteil
macht die Originalaufgabenstellung offenbar doch Sinn:
Ausgabe S fuer n = 0 ist S = 1
Vergleich mit [mm] 2^n: [/mm] 1
Weiter geht's!
Ausgabe S fuer n = 1 ist S = 2
Vergleich mit [mm] 2^n: [/mm] 2
Weiter geht's!
Ausgabe S fuer n = 2 ist S = 4
Vergleich mit [mm] 2^n: [/mm] 4
Weiter geht's!
Ausgabe S fuer n = 3 ist S = 8
Vergleich mit [mm] 2^n: [/mm] 8
Ich werde aber wohl heute eher nicht dazu kommen, nochmal genauer
über die Aufgabe nachzudenken...
Gruß,
Marcel
|
|
|
|
![[]](/images/popup.gif){kind=small}
Wolfram|Alpha