Modulo 2 Binomial Transform
Alec Mihailovs
alec at mihailovs.com
Sun Dec 26 03:56:47 CET 2004
From: Paul D. Hanna
Sent: Saturday, December 25, 2004 6:09 PM
> Is it easy to prove that the following sum is equal to the product below?
> Sum_{k=0..n} M^A000120(n-k)*(C(n,k) Mod 2)*B^k =
> Product_{k=0..[log_2(n)]} ( B^(2^k) + M )^b(n,k)
> where A000120(k) = number of 1's in binary expansion of k
> and where b(n,k) = coefficient of 2^k in the binary expansion of n.
Yes, that's easy. Notice that
(x+y^a_1)...(x+y^a_m) = x^m + x^(m-1) (y^a_1+...+y^a_m) +
x^(m-2) (y^(a_1+a_2) + ... + y^(a_i + a_j) + ... ) + ...
that gives the identity above after substituting x = M, y = B,
m=A000120(n), and n = a_1 + a_2 +... + a_m is the representation of n in
binary system, eg.
for n=11, a_1 = 8, a_2 = 2, a_3 =1. Notice that C(n,k)=1 mod 2 if and only
if k is a sum of some of a_i.
Alec Mihailovs
http://math.tntech.edu/alec/
More information about the SeqFan
mailing list