MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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]:="]
>>
>>
>>
>


  • Prev by Date: Re: Re: Zero testing
  • Next by Date: Re: Re: Zero testing
  • Previous by thread: Re: Help with a summation
  • Next by thread: Plot with x axis in dB