Re: Help with a summation
- To: mathgroup at smc.vnet.net
- Subject: [mg53170] Re: [mg53150] Help with a summation
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Mon, 27 Dec 2004 06:41:46 -0500 (EST)
- References: <200412250900.EAA18567@smc.vnet.net> <3EBCF74E-57BB-11D9-9B3E-000A95B4967A@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
One more thing just came to my mind. This identity looks very much like
some of the identities in Chapter 5 of Knuth's "Concrete Mathematics"
and ought to be provable using techniques described there.
Andrzej
On 27 Dec 2004, at 12:56, Andrzej Kozlowski wrote:
> Unfortunately Mathematica seems unable to prove this identity in
> general. At least the best I have been able to do with it is to verify
> the identity for a given pair of integers n and k, with n> k and for
> arbitrary S.
>
> First we slightly redefine your functions, using a singe function name:
>
> PS[n_, k_, S_, S_] =
> FullSimplify[
> Sum[(1/(j + 1))*Binomial[
> n - 1, j]*(1/S)^j*
> (1 - 1/S)^(n - 1 - j),
> {j, k, n - 1}],
> {s > 0, S > 0, n > 0}];
>
>
> PS[n_, k_, 1, S_] = FullSimplify[
> Sum[(Binomial[n - 1, k - i]*(1 - 1/S)^(k - i)*
> (1/S)^(i - k + n - 1))/(i - k + n), {i, 0, k}],
> {s > 0, S > 0, n > 0}];
>
>
> PS[n_, k_, s_, S_] = FullSimplify[
> Sum[(Binomial[n - 1, k - i]*(1 - s/S)^(k - i)*
> Binomial[(n - 1) - (k - i), j]*(1/S)^j*
> ((s - 1)/S)^((n - 1) - (k - i) - j))/(j + 1),
> {i, 0, k}, {j, i, n - 1}], {s > 0, S > 0, n > 0}];
>
> Mathematica usually expresses such sums in terms of generalised
> functions, when it can find the sums, which is in the case of the
> first and second definition above but not in the third.
>
> PS[n,k,S,S]//InputForm
>
>
> ((-1 + S)^(-1 - k + n)*S^(1 - n)*Gamma[n]*
> Hypergeometric2F1Regularized[1, 1 + k - n, 2 + k,
> (1 - S)^(-1)])/Gamma[-k + n]
>
>
> PS[n,k,s,S]//InputForm
>
> Sum[((-1 + s)^(-1 + i - j - k + n)*S^(1 - n)*
> (-s + S)^(-i + k)*Gamma[n])/(Gamma[2 + j]*
> Gamma[1 - i + k]*Gamma[i - j - k + n]), {i, 0, k},
> {j, i, -1 + n}]
>
> Let's now define the function we would like to prove is zero:
>
> f[n_, k_, S_] := Sum[PS[n, k, p, S], {p, 1, S}] - S/n
>
> We can use it to numerically verify your claim for a symbolic S. This
> works even without using FullSimplify:
>
> f[#,Random[Integer,{1,10}],S]&/@Range[20,30]
>
>
> {0,0,0,0,0,0,0,0,0,0,0}
>
> Unfortunately using FullSimplify on f does not help:
>
> In[10]:=
> FullSimplify[f[n, k, S],
> (k | n | S) $B":(B Integers &&
> n > k && n > 0 && k > 0 &&
> S > 0]
>
> Out[10]=
> -(S/n) + Sum[
> ((-1 + p)^(-1 + i - j - k +
> n)*S^(1 - n)*(-p + S)^
> (-i + k)*Gamma[n])/
> (Gamma[2 + j]*Gamma[
> 1 - i + k]*Gamma[
> i - j - k + n]),
> {p, 1, S}, {i, 0, k},
> {j, i, -1 + n}]
>
>
> All we get is the identity to be proved in a somewhat different form.
> What's worse is that using FullSimplify with a numerical S and
> arbitrary n and k gives an error:
>
>
> FullSimplify[h[n, k, S] /. S -> 10,
> (k | n) $B":(B Integers && n > k && n > 0 &&
> k > 0]
>
> Infinite expression 1/0 encountered.
>
> Indeterminate
>
> The same happens with f instead of h.
>
>
> Andrzej Kozlowski
> Chiba, Japan
> http://www.akikoz.net/~andrzej/
> http://www.mimuw.edu.pl/~akoz/
>
>
>
>
>
>
> On 25 Dec 2004, at 18:00, m.elhaddad at gmail.com wrote:
>
>> Hi All,
>>
>> I'm trying to use mathematica to verify the value of a summation. It
>> runs for a long time without returning a solution. I'm not sure my
>> input to Mathematica is in the proper form.
>>
>> I'm including the mathematica cell expressions below. There I define
>> three functions
>> PS(N,k,s,S): defined for 1<s<S
>> PS1(N,k,S): defined at s=1, and
>> PSS(N,k,S): defined at s = S.
>>
>> Each of these functions is a summation. I'd like to verify that
>> for any k,N, and S>2: PS1+PSS+sum_{2<s<S}PS = S/N, which seems to be
>> a
>> correct by numerical evaluation.
>>
>> Doing it by hand appears to be beyond my reach. I'd appreciate your
>> help whether you can see that it holds (or not), or know how to get
>> mathematica to work it out.
>>
>> Thanks,
>> --MH
>>
>> These are the four cell expressions:
>>
>> Cell[BoxData[
>> RowBox[{
>> RowBox[{"PS", "[",
>> RowBox[{"N_", ",", "k_", ",", "s_", ",", "S_"}], "]"}], " ",
>> ":=",
>> " ",
>> RowBox[{
>> UnderoverscriptBox["\[Sum]",
>> RowBox[{"i", "=", "0"}], "k"],
>> RowBox[{"(", " ",
>> RowBox[{
>> UnderoverscriptBox["\[Sum]",
>> RowBox[{"j", "=", "i"}],
>> RowBox[{"N", "-", "1"}]],
>> RowBox[{"(",
>> RowBox[{
>> FractionBox["1",
>> RowBox[{"j", "+", "1"}]], " ",
>> RowBox[{"Binomial", "[",
>> RowBox[{
>> RowBox[{"N", "-", "1"}], ",",
>> RowBox[{"k", "-", "i"}]}], "]"}], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> RowBox[{"1", "-",
>> FractionBox["s", "S"]}], ")"}],
>> RowBox[{"k", "-", "i"}]],
>> RowBox[{"Binomial", "[",
>> RowBox[{
>> RowBox[{
>> RowBox[{"(",
>> RowBox[{"N", "-", "1"}], ")"}], "-",
>> RowBox[{"(",
>> RowBox[{"k", "-", "i"}], ")"}]}], ",", "j"}],
>> "]"}], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> FractionBox["1", "S"], ")"}], "j"], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> FractionBox[
>> RowBox[{"s", "-", "1"}], "S"], ")"}],
>> RowBox[{
>> RowBox[{"(",
>> RowBox[{"N", "-", "1"}], ")"}], "-",
>> RowBox[{"(",
>> RowBox[{"k", "-", "i"}], ")"}], "-", "j"}]]}],
>> ")"}]}], ")"}]}]}]], "Input"]
>>
>> Cell[BoxData[
>> RowBox[{
>> RowBox[{"PS1", "[",
>> RowBox[{"N_", ",", "k_", ",", "S_"}], "]"}], " ", ":=", " ",
>> RowBox[{
>> UnderoverscriptBox["\[Sum]",
>> RowBox[{"i", "=", "0"}], "k"],
>> RowBox[{"(",
>> RowBox[{
>> RowBox[{"Binomial", "[",
>> RowBox[{
>> RowBox[{"N", "-", "1"}], ",",
>> RowBox[{"k", "-", "i"}]}], "]"}], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> RowBox[{"1", "-",
>> FractionBox["1", "S"]}], ")"}],
>> RowBox[{"k", "-", "i"}]], " ",
>> FractionBox["1",
>> RowBox[{"N", "-", "k", "+", "i"}]], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> FractionBox["1", "S"], ")"}],
>> RowBox[{"N", "-", "1", "-", "k", "+", "i"}]]}], " ",
>> ")"}]}]}]], "Input"]
>>
>> Cell[BoxData[
>> RowBox[{
>> RowBox[{"PSS", "[",
>> RowBox[{"N_", ",", "k_", ",", "S_"}], "]"}], " ", ":=", " ",
>>
>> RowBox[{
>> UnderoverscriptBox["\[Sum]",
>> RowBox[{"j", "=", "k"}],
>> RowBox[{"N", "-", "1"}]],
>> RowBox[{"(",
>> RowBox[{
>> FractionBox["1",
>> RowBox[{"j", "+", "1"}]], " ",
>> RowBox[{"Binomial", "[",
>> RowBox[{
>> RowBox[{"N", "-", "1"}], ",", "j"}], "]"}], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> FractionBox["1", "S"], ")"}], "j"], " ",
>> SuperscriptBox[
>> RowBox[{"(",
>> RowBox[{"1", "-",
>> FractionBox["1", "S"]}], ")"}],
>> RowBox[{"N", "-", "1", "-", "j"}]]}],
>> ")"}]}]}]], "Input"]
>>
>> Cell[BoxData[
>> RowBox[{"FullSimplify", "[",
>> RowBox[{
>> RowBox[{
>> RowBox[{"PS1", "[",
>> RowBox[{"N", ",", "k", ",", "S"}], "]"}], "+",
>> RowBox[{"PSS", "[",
>> RowBox[{"N", ",", "k", ",", "S"}], "]"}], "+",
>> RowBox[{
>> UnderoverscriptBox["\[Sum]",
>> RowBox[{"s", "=", "2"}], "S"],
>> RowBox[{"PS", "[",
>> RowBox[{"N", ",", "k", ",", "s", ",", "S"}], "]"}]}]}],
>> ",", " ",
>> RowBox[{"S", ">", "2"}]}], "]"}]], "Input",
>> CellLabel->"In[6]:="]
>>
>>
>>
>
- References:
- Help with a summation
- From: m.elhaddad@gmail.com
- Help with a summation