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} $$
I want to define a $$f(n) = \sum_{m=1}^{2^n}\prod_{i=1}^n row_mcol_i$$
I'm not sure if I wrote the above equation correctly but in words it is the following, for each row multiply the columns values together and add it to the result of the previous row.
e.g from the table above we would have the following:
$$f(3) = 1 + g(0) + g(1) + g(0)g(1) + g(2) + g(2)g(0) + g(2)g(1) + g(2)g(1)g(0)$$
Any help in generalising the equation for $f(n)$ would be much appreciated. The tables above are merely to help illustrate the pattern, if possible I would prefer not to reference the rows and columns of some matrix.
Thanks in advance.
This is just $$(1+g(0))(1+g(1))(1+g(2))\dots(1+g(n-1))$$
This could be written as:
$$\prod_{k=0}^{n-1} (1+g(k))$$
Your expression could be written by defining $G(m,k)$ as $1$ if $m$ has zero in the $k$th bit and $g(k)$ otherwise. Then you want:
$$\sum_{m=0}^{2^n-1}\prod_{k=0}^{n-1} G(m,k)$$
But this simplifies to my above expression.
An alternative formulation is to define $[n]=\{0,1,\dots,n-1\}$ and then you can write your formula as:
$$\sum_{S\subseteq [n]} \prod_{k\in S} g(k)$$
This uses the fact that the numbers from $0$ to $2^n-1$ encode the subsets of $[n]$.