Auswahl Schwarzes Brett Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
  Umgang mit Binomialkoeffizienten, Abelsche Summe |
|
Newmath2012
Aktiv 
Dabei seit: 26.09.2013
Mitteilungen: 302
 |
Hallo allerseits,
mithilfe der Abelschen Summationsformel möchten wir \(\sum_{1 \leq k < n} \binom k m H_k\) berechnen.
Ich vermute, dass H_k das k-te harmonische Mittel bezeichnet. Mir ist allerdings in der Angabe nicht klar, wie die Binomialkoeffizienten existieren können oder zu behandeln sind, da ja m nicht eingeschränkt wird, also durchaus größer als 1 sein könnte und dann wäre z.B. der erste Summand für k=1 nicht wohldefiniert oder?
Wie würdet ihr das verstehen?
|
 Profil
 Quote
 Link |
Nuramon
Senior 
Dabei seit: 23.01.2008
Mitteilungen: 1192
|      Beitrag No.1, eingetragen 2018-10-06
|
\(\begingroup\)\(\newcommand{\End}{\operatorname{End}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\GL}{\operatorname{GL}}\)
Hallo,
für $k\in\IN$ und $m>k$ definiert man $\binom km :=0$.
Das hat unter anderem zur Folge, dass die binomische Formel $(1+X)^k = \sum_{m=0}^\infty {k \choose m} X^m$ gilt.\(\endgroup\)
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.2, vom Themenstarter, eingetragen 2018-10-07
|
Danke für deine Antwort, Nuramon!
Leider bin ich damit noch nicht so gut vorangekommen wie erhofft.
Ich habe mehrfach versucht, die abelsche Summation für die Berechnung sinnvoll anzwenden (und habe dabei ein paar Mal zum Schluss nach den Umformungen genau wieder den zu berechnenden Ausdruck erhalten...).
Meine bisher sinnvollste Version ist folgende:
Die abelsche Summationsformel lautet: \(\sum_{k=1}^N a_k b_k = a_N \sum_{k=1}^N b_k - \sum_{k=1}^{N-1}(a_{k+1}-a_k)\sum_{i=1}^k b_i\)
Darum setze ich \(a_k:=\binom {k} {m}, b_k:=H_k\) und erhalte unter Verwendung von \(\sum_{k=1}^{n-1}H_k = n\cdot (H_n-1)\) und \(\sum_{k=1}^{n-2}(\binom {k+1}{ m} - \binom{k}{m}) = \binom{n-1}{m}-\binom{i}{m}\),
die Gleichheit \( \sum_{k=1}^{n-1}\binom{k}{m}H_k = \sum_{k=1}^{n-2} \binom{k}{m} H_k + \binom{n-1}{m}\cdot n \cdot (H_n-1)-\binom{n-1}{m}\cdot (n-1) \cdot (H_{n-1}-1)\)
Wolfram-Alpha gibt für den zu berechnenden Ausdruck leider eine elends lange Formel aus, daher weiß ich nicht genau, worauf das Beispiel hinauslaufen soll.
Hast du Nuramon, oder hat jemand anderer, eine Idee, wie man da mit der Abelschen Summationsformel den Ausdruck noch besser "berechnen" kann oder was herauskommen soll?
|
Profil
Quote
Link |
endy
Senior 
Dabei seit: 10.01.2011
Mitteilungen: 3154
 | Beitrag No.3, eingetragen 2018-10-07
|
Hallo.
Vertausche in deinem Ansatz die harmonischen Zahlen und die Bikos.Dann wird alles gut.
Gruß endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.4, vom Themenstarter, eingetragen 2018-10-07
|
Hallo endy,
danke für den Tipp!
Nun erhalte ich unter Verwendung von \(\sum_{k=1}^{n-1}\binom{k}{m} - \sum_{k=1}^{n-2} \binom{k}{m} = \frac{(n-m)\cdot \binom{n}{m} + (m-1)\cdot \binom{1}{m}}{m+1} - \frac{(-m+n-1)\cdot \binom{n-1}{m} + (m-1) \cdot \binom{1}{m}}{m+1}\) und \(\sum_{k=1}^{n-1}\binom{k}{m} = \frac{(n-1-m)\cdot \binom{n-1}{m} + (m-1)\cdot \binom{1}{m}}{m+1}\) (was ich hoffe, einfach so verwenden zu dürfen),
dass:
\(\sum_{k=1}^{n-1}H_k\cdot \binom{k}{m} = H_{n-1} \cdot (\frac{(n-m) \cdot \binom{n}{m} - (n-1-m) \cdot \binom{n-1}{m}}{m+1}) + (\frac{(n-1-m)\cdot \binom {n-1}{m} + (m-1)\cdot \binom{1}{m}}{m+1})\).
Ist das nun der "schönste"/"beste" Ausdruck, den man mithilfe der Abelschen Summationsformel erhalten kann oder soll etwas anderes herauskommen?
|
Profil
Quote
Link |
endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3154
| Beitrag No.5, eingetragen 2018-10-07
|
Hallo.
Ich rechne einmal:
Mit  und  folgt:
 via Teleskopsumme und der Fundamentalgleichung des Pascaldreiecks für m ungleich -1.
Es gilt weiterhin  .
Für die Gesamtsumme ergibt sich also
Gruß endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.6, vom Themenstarter, eingetragen 2018-10-08
|
Hallo endy, danke für deine Bemühungen!
Ich kann deine Rechnung leider nicht nachvollziehen.
Was \(\sum_{k=1}^{n-1}b_k\) betrifft, so habe ich verwendet, dass \(b_k = \binom{k}{m} = \binom{k+1}{m+1}-\binom{k}{m+1}\) ist. Dann kommt bei mir aber \(\binom{n}{m+1} - \binom{1}{m+1}\) heraus, weil der unterste Summand mir nicht wegfällt und er nicht zwingend 0 ist?
Führst du bei deiner Rechnung eine Vertauschung von Doppelsummen durch?
Ich habe versucht, dein Zwischenergebnis \(\frac{1}{m+1}\sum_{k=1}^{n-2}\binom{k}{m}\) herzuleiten, aber bei mir sieht das nur so aus:
\(\sum_{k=1}^{n-2}(a_{k+1}-a_k)\cdot \sum_{j=1}^k b_j = \)Abel anwenden \(= a_{n-1}\cdot \sum_{k=1}^{n-1}b_k - \sum_{k=1}^{n}a_k\cdot b_k \)
\(=a_{n-1}\cdot (\binom{n}{m+1}-\binom{1}{m+1}) - \sum_{k=1}^n(\sum_{j=1}^k \frac{1}{j})\cdot b_k\)
Hier wüsste ich nicht weiter, daher vertausche ich die Doppelsummen, um über die bk summieren zu können. Dann erhalte ich:
\(=a_{n-1} \cdot (\binom{n}{m+1}-\binom{1}{m-1}) - \sum_{j=1}^n \frac{1}{j} \cdot (\binom{n}{m+1} - \binom{j-1}{m+1})\)
Kannst du mir bitte verraten, wo du anders umformst als ich?
EDIT:
Hallo endy, mir ist jetzt klar, wie du die Abelsche Summation anwendest. - Du berechnest beide Summanden in der Gleichung einzeln. Der erste Summand ist mir klar (bis auf das oberhalb geschilderte Problem, dass bei mir bei der Teleskopsumme der unterste Summand auch noch da ist).
Wie aber bei dir die mit "..." abgekürzten Umformungen aussehen, schaffe ich nicht nachzuvollziehen. Ich habe dafür nun: \(\sum_{k=1}^{n-2}(a_{k+1}-a_k)\sum_{j=1}^kb_j = \sum_{k=1}^{n-2}\frac{1}{k+1}\binom{k}{m}\)
|
Profil
Quote
Link |
endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3154
| Beitrag No.7, eingetragen 2018-10-08
|
EDIT:
Hallo endy, mir ist jetzt klar, wie du die Abelsche Summation anwendest. - Du berechnest beide Summanden in der Gleichung einzeln. Der erste Summand ist mir klar (bis auf das oberhalb geschilderte Problem, dass bei mir bei der Teleskopsumme der unterste Summand auch noch da ist).
Wie aber bei dir die mit "..." abgekürzten Umformungen aussehen, schaffe ich nicht nachzuvollziehen. Ich habe dafür nun: \(\sum_{k=1}^{n-2}(a_{k+1}-a_k)\sum_{j=1}^kb_j = \sum_{k=1}^{n-2}\frac{1}{k+1}\binom{k}{m}\)
Der untere Summand der Teleskopsumme verschwindet.
Es gilt
Gruß endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.8, vom Themenstarter, eingetragen 2018-10-08
|
Danke endy, das ist mir nun klar! :)
Das Einzige, das ich noch nicht kapiert habe, ist, WARUM der unterste Summan der Teleskopsumme verschwindet, also etwa \(\sum_{k=1}^{n-1}\binom{k}{m} = \binom{n}{m+1}-\binom{1}{m+1}\) NICHT gilt, sondern der letzte Ausdruck wegfällt?
|
Profil
Quote
Link |
endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3154
| Beitrag No.9, eingetragen 2018-10-09
|
Dies gilt natürlich.Aber der letzte Term ist für positive natürliche Zahlen immer 0.
mathematica (* In *)
Clear @ "Global`*"
a[m_] := Binomial[1, m + 1]
a /@ Range @ 100
(* Out *)
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0}
|
Dies ergibt sich aus der Definition der Binomialkoeffizienten.
endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.10, vom Themenstarter, eingetragen 2018-10-09
|
Okay, für positive Zahlen gilt es freilich nach Definition.
Ich hatte aber geglaubt, du meinst, dass es auch für den Fall m=0 wegfällt (denn aus welcher Teilmenge der ganzen Zahlen m ist, ist ja nicht angegeben, deshalb auch meine Frage zu Beginn, was passiert wenn der obere Eintrag im Binomialkoeffizienten kleiner ist als der untere).
Aber dann werde ich einfach annehmen, dass m positiv ist.
Danke für deine Hilfe! :)
|
Profil
Quote
Link |
endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3154
| Beitrag No.11, eingetragen 2018-10-10
|
(2018-10-07 05:24 - Newmath2012 in Beitrag No. 2
...
Wolfram-Alpha gibt für den zu berechnenden Ausdruck leider eine elends lange Formel aus, daher weiß ich nicht genau, worauf das Beispiel hinauslaufen soll.
... mathematica (* In *)
a[n_, m_] := Sum[Binomial[j, m]*HarmonicNumber[j], {j, 1, n - 1}]
sol1 = a[n, m]
sol2 = sol1 // FullSimplify
(* Out *)
(1/(2 (1 + m)^2 (1 + n)))(-2 Binomial[1, m] + 2 m^2 Binomial[1, m] -
2 n Binomial[1, m] + 2 m^2 n Binomial[1, m] + 2 Binomial[2, m] -
3 m Binomial[2, m] + m^2 Binomial[2, m] + 2 n Binomial[2, m] -
3 m n Binomial[2, m] + m^2 n Binomial[2, m] +
2 m Binomial[1 + n, m] - 2 m^2 Binomial[1 + n, m] -
2 n Binomial[1 + n, m] + 4 m n Binomial[1 + n, m] -
2 n^2 Binomial[1 + n, m] - 2 m Binomial[n, m] HarmonicNumber[n] -
2 m^2 Binomial[n, m] HarmonicNumber[n] +
2 n Binomial[n, m] HarmonicNumber[n] -
2 m^2 n Binomial[n, m] HarmonicNumber[n] +
2 n^2 Binomial[n, m] HarmonicNumber[n] +
2 m n^2 Binomial[n, m] HarmonicNumber[n])
-((Gamma[1 + n]/(
Gamma[1 + m] Gamma[-m + n]) + (1 + m) (m - n) Binomial[n,
m] HarmonicNumber[n] + Sin[m \[Pi]]/\[Pi])/(1 + m)^2)
|
Die erste Lösung ist wirklich ziemlich schlecht,aber die zweite Lösung schon deutlich übersichtlicher.
Es geht aber noch viel besser.
Man siehe The summation package Sigma
Man downloade es und starte es.
Mit dem Helpbutton wird die Benutzung des Packages erklärt.
mathematica (* In *)
mysum = SigmaSum[SigmaBinomial[j, m] SigmaHNumber[j], {j, 1, n - 1}];
sol = SigmaReduce[mysum, n]
(* Out *)
-Subscript[H, m] + (-(n/(1 + m)^2) + (n Subscript[H, n])/(1 + m))
\!\(\*SuperscriptBox[\((\*GridBox[{
{
RowBox[{
RowBox[{-, 1}], +, n}]},
{m}
}])\), \(.\)]\) + \!\(
\*UnderoverscriptBox[
SuperscriptBox[\(\[Sum]\), \(.\)], \(j = 1\), \(m\)]\(
\*SubscriptBox[\(H\), \(j\)]\ \*
SuperscriptBox[
RowBox[{"(", GridBox[{
{"j"},
{"m"}
}], ")"}], "."]\)\) |
Der Output wird hier leider nicht sehr schön dargestellt.Man kopiere ihn daher in ein mathematica Notebook.
Man erkennt sofort,dass sich links das  und die rechte Summe wegcanceln und es folgt nahezu sofort die Lösung wie am Ende von Beitrag Nr.5 angegeben.
Gruß endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.12, vom Themenstarter, eingetragen 2018-10-20
|
Hallo endy,
dankeschön für diese Ergänzung!
Eine meiner größten mathematischen Schwachstellen ist, dass ich nicht mit mathematica umgehen kann, da ist deine Codevorlage Gold wert. :)
|
Profil
Quote
Link |
endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3154
| Beitrag No.13, eingetragen 2018-10-25
|
Deutlich eleganter kann man die Aufgabe übrigens mittels Differenzenrechnung und diskreter partieller Integration lösen.
Man siehe z.B.
Martin Aigner : Diskrete Mathematik.Kapitel 2.2.
endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.14, vom Themenstarter, eingetragen 2018-10-27
|
Okay, danke! Wenn ich das Buch auftreibe, werde ich es mir ansehen. :)
|
Profil
Quote
Link |
endy
Senior
Dabei seit: 10.01.2011
Mitteilungen: 3154
| Beitrag No.15, eingetragen 2018-11-27
|
Noch einmal hierzu
2018-10-07 05:24 - Newmath2012 in Beitrag No. 2 schreibt:
...
Wolfram-Alpha gibt für den zu berechnenden Ausdruck leider eine elends lange Formel aus, daher weiß ich nicht genau, worauf das Beispiel hinauslaufen soll.
...
Man siehe dazu Klick mich.
mathematica (* In *)
f[k_, m_] := Binomial[k, m] HarmonicNumber[k]
solution1 = telescopSum[f[k, m], {k, 1, n - 1}, Certificate -> True]
solution2 = solution1 // FullSimplify
solution3 =
solution2 //
FullSimplify[#, Assumptions -> Element[m, Integers] && m >= 1] &
(* Output von solution3 *)
{(Gamma[1 + n] (-1 + (1 + m) HarmonicNumber[n]))/((1 +
m)^2 m! Gamma[-m + n]), (
k Gamma[k] (-1 + (1 + m) HarmonicNumber[k]))/((1 + m)^2 m! Gamma[
k - m])}
|
Mma ( - in diesem Fall Version 10 - ) kann also das gewünschte Ergebnis modulo ein paar trivialen Umformungen berechnen und liefert auch noch den "Beweis" dazu.
endy
|
Profil
Quote
Link |
Newmath2012
Aktiv
Dabei seit: 26.09.2013
Mitteilungen: 302
| Beitrag No.16, vom Themenstarter, eingetragen 2018-12-01
|
Oh, das ist sehr nützlich, danke! :)
|
Profil
Quote
Link |
|
Home
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]