Bell numbers

[Olivier Gerard]

Jeffrey and seqfans,

it was on Number-Theory:


Delivery-date: Thu, 28 Jun 2001 14:54:18 +0200
X-From_: owner-nmbrthry at LISTSERV.NODAK.EDU Thu Jun 28 14:51:57 2001
Reply-To: Dan Fux <danfux at my-deja.com>
From: Dan Fux <danfux at my-deja.com>
Subject:      Bell numbers
To: NMBRTHRY at LISTSERV.NODAK.EDU

Ahmed Fares asked me to post this :

I posted recently a new sequence to the EIS of Neil Sloane , here is
the description:

ID Number: A061462
1,1,2,1,1,4,1,1,4,1,1,2,1,1,2,1,1,4,...
The exact power of 2 that divides the n-th Bell number (sequence A000110) .
It looks like a(n) = 1 if n = 0 or 1 mod 3 and that a pattern exists also
for n = 2 mod 3 but I don't have a formula yet .

Can someone help about the formula for this sequence ?

Thanks,Ahmed


----- Forwarded message from Don Coppersmith <COPPER at watson.ibm.com> -----

Delivery-date: Thu, 28 Jun 2001 19:53:51 +0200
X-From_: owner-nmbrthry at LISTSERV.NODAK.EDU Thu Jun 28 19:51:45 2001
Reply-To: Don Coppersmith <COPPER at watson.ibm.com>
From: Don Coppersmith <COPPER at watson.ibm.com>
Subject:      Bell numbers
To: NMBRTHRY at LISTSERV.NODAK.EDU

Ref:  Your note of Thu, 28 Jun 2001 08:51:51 -0400

To show a(n) mod 2 is periodic with period 3, with values (1,1,0),
you can use the recursive definition a(n+1) = Sum a(k)C(n,k).
Let w be a primitive cube root of 1.
Assume that for n' \leq n we know a(n')=1 mod 2 if n'=0 or 1 mod 3,
and 0 mod 2 otherwise, and prove it for a(n+1).
w*(-w^{-1})^n = w*(1+w)^n           = Sum C(n,k)w^{k+1}.
w^{-1}*(-w)^n = w^{-1}+(1+w^{-1})^n = Sum C(n,k)w^{-k-1}.
Adding,
(-1)^n (w^{-n+1}+w^{n-1})
= Sum C(n,k)(-1 if k=0 or 1 mod 3, 2 if k=2 mod 3)
= Sum C(n,k)a(k) mod 2
= a(n+1) mod 2.
And left-hand side is even iff n=1 mod 3.  That proves it.

To show a(n) mod 4 periodic with period 12, one could use
12th roots of unity; and to show a(n) mod 8 periodic with period 24,
one could use 24th roots of unity.  I haven't tried either one.
Exercise for the reader.

Don Coppersmith   copper at watson.ibm.com  dcopper at us.ibm.com