Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is similar to a question I asked here but now I need to alter it so I have brought across the relevant parts.

Given a binary table with n bits as follows:

$$\begin{array}{cccc|l} 2^{n-1}...&2^2&2^1&2^0&row\\ \hline \\ &0&0&0&1 \\ &0&0&1&2 \\ &0&1&0&3 \\ &0&1&1&4 \\ &1&0&0&5 \\ &1&0&1&6 \\ &1&1&0&7 \\ &1&1&1&8 \end{array} $$

If I replace each $0$ with a $1$ and each $1$ with $g(n)$ as follows

$$\begin{array}{cccc|l} 2^{n-1}...&2^2&2^1&2^0&row\\ \hline \\ &1&1&1&1 \\ &1&1&g(0)&2 \\ &1&g(1)&1&3 \\ &1&g(1)&g(0)&4 \\ &g(2)&1&1&5 \\ &g(2)&1&g(0)&6 \\ &g(2)&g(1)&1&7 \\ &g(2)&g(1)&g(0)&8 \end{array} $$

If I multiply the values in a row together and add up each row, thanks to Thomas Andrews, I now know that I can represent it as follow: $$f(n) = \prod_{k=0}^{n-1} (1+g(k))$$

But now I want to be more selective about the rows that I am adding, instead of adding all of them I only want to add rows that have a $2^x$ number of $g(k)$'s. i.e add all of the rows that have $2,4,8...$ g(k)'s in them.

In my example table above I would add rows 4,6,7 together as these each have 2 $g(k)$'s in them. If n=4 in my above example them we would also need to add row 16 as it would have 4 g(k)'s in its row. If n=5 there would be 5 such rows that have 4 g(k)s in them. I hope this makes sense.

If I were only concerned with rows that have 2 $g(k)$'s in them I could have something as follows:$$f(n) = \sum_{j=1}^{n-1} \sum_{k=j+1}^n g(j)g(k)$$

I can't seem to extend this to all $2^x$ rows and not only $2^1$ rows. I was considering some recursive function but can't seem to figure it out. Any help would be much appreciated.

Thanks in advance!

share|cite|improve this question

Following the interpretation that you have, consider the expansion as $f(n, x) = \prod ( 1 + g(n) x )$, and then find the coefficients of the terms of degree $2^k$, and then add them up.

This is equivalent to adding it up manually though.

If you want to find the sum of those with an even number of $g(k)$, then that is much more approachable.

share|cite|improve this answer
Thanks for the answer, i'm struggling to understand it though. Would you mind explaining the expansion a little, im not sure what you are iterating on n or x? – Manatok May 25 '13 at 9:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.