Modulo 2 Binomial Transform

[Paul D. Hanna]

I made a typo in (1) - it should have read A000120(n-k) not A000120(k); 
the correct formula is given below. 
 
The formula for the (Mod 2 Binomial transformation)^M of A is: 
(1)  a(n) = Sum_{k=0..n} M^A000120(n-k)*(C(n,k) Mod 2)*A(k) 
 
Again, the transform has nice factorization properties for A(n)=B^n. 
 
Is it easy to prove that the following sum is equal to the product below?
(empirically, this holds true to at least n=4096 for all integer B and
M). 
 
  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. 
 
This PARI code gives the difference of these two formulas, and 
returns all zeros for all B and M up to n=4096: 
a(n)=sum(k=0,n,M^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*B^k)
b(n)=prod(k=0,length(binary(n))-1,(B^(2^k)+M)^bittest(n,k)) 
for(n=0,4096,print1(a(n)-b(n),","))
 
Thanks,
        Paul
------------------------------------------------------------------------
On Sat, 25 Dec 2004 16:28:56 -0500 Paul D. Hanna <pauldhanna at juno.com>
writes:
One last note regarding Paul Barry's Modulo 2 Binomial Transform. 

If we apply the triangle formed by reading Pascal's triangle mod 2: 
http://www.research.att.com/projects/OEIS?Anum=A047999 
as a transformation on a sequence A, and apply this transform M times, 
the formula for this (Mod 2 Binomial transformation)^M of A is: 

(1)  a(n) = Sum_{k=0..n} M^A000120(k)*(C(n,k) Mod 2)*A(k) 
where A000120(k) = number of 1's in binary expansion of k. 

This can be expressed using PARI code as:
a(n)=sum(k=0,n,M^subst(Pol(binary(n-k)),x,1)*(binomial(n,k)%2)*A(k))

  
A special case exists when A(n) = B^n for integer B; 
for then (1) is equivalent to the product formula: 
  
(2)  a(n) = Product_{k=0..[log_2(n)]} ( B^(2^k) + M )^b(n,k) 
where b(n,k) = coefficient of 2^k in the binary expansion of n. 
  
This can be expressed using PARI code as:
a(n)=prod(k=0,length(binary(n))-1,(B^(2^k)+M)^bittest(n,k)) 
  
The product formula (2) explains the factorization behavior noted
earlier. 

(Merry Christmas)^2,
      Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20041225/82a0b8f3/attachment-0001.htm>