Modulo 2 Binomial Transform

[Alec Mihailovs]

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/