I'm pretty much stuck with the following problem:

A boolean function B(m,n) of m variables evaluates to 1 only if at least n variables are 1.

How many nodes do you need in a decision tree to represent this function (the formula with explanation)?

This is what I've come up with so far:

1. the problem is recursive:

Going from the the first node (first variable) - on the branch where n1 = 1 the problem becomes B(m-1,n-1). On the other branch (n1 = 0) it becomes B(m-1,n). etc

2. The formula will have a binomial coefficient (because at least n out of m variables must evaluate to 1).

Empirically (by counting the nodes in trees with small m) I've come up with:

2 * (m+1 choose n) - 1 , but the explanation why this is true is beyond me.

I have virtually no background in discrete mathematics and it seems like I'm running in circles with this. Any hints or corrections will be more than welcome.