[seqfan] Re: A sequence relating to A157019

Max Alekseyev maxale at gmail.com
Wed Dec 2 17:45:06 CET 2009

```On Wed, Dec 2, 2009 at 6:01 AM,  <franktaw at netscape.net> wrote:
> I was looking at this sequence, Sum_{d|n} binomial(n/d+d-2,d-1), which
> has generating function Sum_{n>=1} x^n/(1 - x^n)^n, and decided to look
> at the related g.f. Sum_{n>=1} x^n/(1 + x^n)^n.  This sequence starts:
>
> 1, 0, 2, -2, 2, 0, 2, -8, 8, 0, 2, -12, 2, 0, 32, -36, 2, 0, 2, -20,
> 58, 0, 2, -136, 72, 0, 92, -28, 2, 0, 2, -272, 134, 0, 422, -288, 2, 0,
> 184, -480, 2, 0, 2, -44, 1232, 0, 2, -2360, 926, 0, 308, -52, 2, 0,
> 2004, -1176, 382, 0, 2, -4064, 2, 0, 6470, -5128
>
> This appears to be Sum_{d|n} (-1)^(d+1) binomial(n/d+d-2,d-1); I
> haven't actually tried to prove it, but 100 terms match.

The proof of this formula is rather simple. Notice that
[x^m] x^n/(1 + x^n)^n
= 0 if n does not divide m
or
= binomial(-n,(m-n)/n) = (-1)^(m/n-1) * binomial(n+m/n-2,m/n-1)

Summing up over all divisors n of m, we have

a(m) = sum_{n|m} (-1)^(m/n-1) * binomial(n+m/n-2,m/n-1)
= sum_{d|m} (-1)^(d-1) * binomial(m/d+d-2,d-1)
(where d = m/n)

Regards,
Max

```