matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikBinomialkoeffizient
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Diskrete Mathematik" - Binomialkoeffizient
Binomialkoeffizient < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Binomialkoeffizient: Aufgabe
Status: (Frage) überfällig Status 
Datum: 16:44 Do 18.12.2014
Autor: MichaelKelso

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

        
Bezug
Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Binomialkoeffizient: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 07:37 Fr 19.12.2014
Autor: MichaelKelso

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

Bezug
                        
Bezug
Binomialkoeffizient: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Binomialkoeffizient: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 08:20 So 21.12.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Binomialkoeffizient: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:47 So 21.12.2014
Autor: MichaelKelso

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

Bezug
                
Bezug
Binomialkoeffizient: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Binomialkoeffizient: Aufgabenstellung ist doch korr
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Binomialkoeffizient: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:21 So 21.12.2014
Autor: DieAcht

Hallo Marcel,


Ich hatte es letztens auch schon kurzzeitig probiert und hatte
auch die Vermutung, dass die Aufgabe nicht stimmt, allerdings
war dann []Wolfram|Alpha anderer Meinung. Die Aussage stimmt.

Ich probiere es morgen auch noch einmal. Ich mach die Aufgabe
mal auf teilweise beantwortet, vielleicht guckt es sich noch
der eine oder andere an. Die Fälligkeit sollte vielleicht ein
bisschen hochgestellt werden. :-)

Edit: Ich sollte mal die Seite neu laden, wenn ich essen gehe
und dann weiter an meiner Mitteilung schreibe. Du hast es be-
reits berichtigt. ^^


Gruß
DieAcht

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]