I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$

by counting matrices of size $n\times m$ with entries in $\{0,1\}$ such that the sum of columns and rows is odd. One can show that this can only happen if $m,n$ share the same parity.

What are other ways of counting such matrices?

By Davids observation, this is just $2^{(m-1)\times (n-1)}$, which suggests a better counting argument might be produced. Maybe something in the lines of my argument, but completing the $n-1\times m-1$ matrix freely with $1$s and $0$s, and showing its final rows and column may be completed so that it is a solution. I'll think about it.

Proof From $\sum_i a_{ij}=1\mod 2,\sum_j a_{ij}=1\mod 2$, we get $$\sum_i\sum_j a_{ij}=m\equiv n=\sum_j\sum_i a_{ij}\mod 2$$ so that $m,n$ have the same parity. It follows in particular that if a matrix with uneven columns and rows has all rows with an odd number of ones, there exists at least one column with an even number of $1$s. To prove the formula, we can produce an even number of ones in a bitstring of length $m$ in $\sum_{k\;\rm odd}\binom{m}{k}$ ways. Take the first $n-1$ rows and complete so that each has an odd number of ones. I claim the last row may be completed so that every column also has an odd number of ones.

Since the matrix built so far is $n-1\times m$; the first observation says there is a column with an even number of ones, for $m,n-1$ have opposite parity. Put a $1$, to obtain an $n-1\times m-1$ matrix, call it $M$. If $M$ has all columns with an odd number of $1$s, we're done, else there is some column with an even number of $1$s. Insert a $1$ in the corresponding place in the $n$-th row. Then we obtain an $n-1\times m-2$ matrix $M'$ with an odd number of $1$ in the rows (because we deleted $2$ columns, and our original rows had an odd number of ones), so there must exist a column with an even number of $1$s, thus we insert another $1$. Continuing, we see the algorithm stops at an odd numbers of $1$ always, and the proof is complete. The argument is of course symmetric in $m$ and $n$, since the method provides with any matrix of your liking, so the equation follows.

  • $\begingroup$ Doesn't seem right. Can't you just evaluate the sums as $2^m$ and $2^n$, give or take a little? $\endgroup$ – Gerry Myerson Mar 20 '14 at 6:37
  • $\begingroup$ @GerryMyerson I have corrected the formula. It holds say with $n=10,m=2$ to give $2^9=\binom {10} 9+\binom {10} 7+\binom {10 }5+\binom {10} 3+\binom {10} 1=512$. I'm 100% positive my proof is correct. =) $\endgroup$ – Pedro Tamaroff Mar 20 '14 at 6:48
  • $\begingroup$ Then it seems to me the easiest proof is to evaluate each of the sums, as they should both come out to be simple powers of 2. $\endgroup$ – Gerry Myerson Mar 20 '14 at 8:14
  • $\begingroup$ Should there be $\binom nk$ instead of $\binom mk$ in the sum on the RHS? The way it is written now we get for $n=10$ and $m=2$ the sum $\binom21+\binom23+\binom25+\binom27+\binom29=\binom21=2$. $\endgroup$ – Martin Sleziak Mar 20 '14 at 9:24

For $m>0$, we have $\sum_k (-1)^k \binom{m}{k} = (1-1)^m = 0$ and $\sum_k \binom{m}{k} = (1+1)^m = 2^m$. So $$\sum_{k \ \mathrm{odd}} \binom{m}{k} = (2^m-0)/2 = 2^{m-1}.$$

Your identity is $$(2^{m-1})^{n-1} = (2^{n-1})^{m-1}.$$

  • $\begingroup$ Yes, of course. Now I'm thinking the proof I devised might be overly complicated perhaps. $\endgroup$ – Pedro Tamaroff Mar 20 '14 at 14:10
  • $\begingroup$ David: I posted the question a bit late at night, and didn't care to check the observation you make. I am thinking about rephrasing the question to find another counting argument, so I hope you don't mind. I have duly upvoted. $\endgroup$ – Pedro Tamaroff Mar 20 '14 at 14:20

Here's the solution that gives the formula $2^{(n-1)(m-1)}$ right away, and happens to prove what David used.

Fill the $(n-1)(m-1)$ matrix freely. Complete the $n$-th column so the first $m-1$ rows have an odd number of ones, and use the method described in the post to complete the matrix so that it fits the conditions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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