Any way to get a Recursive function from its closed form?

Question

For an exercise, the goal is to find a recursive definition for a certain function.

the function itself is as follows: f(a,b) is the # of binary strings of length a and with b more 1s than 0s.

eg: f(4,0) = 6 (because 1100, 1010, 1001, 0101, 0011, 0110)

So far all I've figured out is a closed form:

I'm just wondering if there's a good way to get a recursive definition for this.

Edit: I forgot to mention that this closed form function only works when a and b are BOTH either ODD or EVEN. This is due to the definition producing 0 strings otherwise.

Many thanks in advance.

Answer 1

You can't (easily) get a recursive function from the closed form, but you can get one from the problem description. First of all, it's obviously impossible for the difference between ones and zeroes to be greater than the total number of digits, so $f(a,b) = 0$ if $b\gt a$; similarly, $f(a,b)=0$ if $-b\gt a$.

There are two different ways of looking at the next step. The simpler one to understand is that there's exactly one sequence — '1' — with one symbol and 1 more 1s than 0s, and one sequence with one symbol and -1 more 1s than 0s — and no sequences with one symbol and the same number of 1s and 0s; in other words, $f(1,1) = f(1,-1) = 1$ and $f(1,0)=0$. But the more fruitful one is to realize that there's exactly one sequence with zero symbols, and 0 more 1s than 0s, namely the empty sequence ''; in other words, $f(0,0)=1$.

Once you have the base case(s) of your recursive definition in place, you can start thinking about the recursive case. In this case, the easiest way to think of it is to consider how your sequence starts. Suppose you've got a sequence of length $n\gt 0$ with $m$ more ones than zeroes; then the first symbol is either a 0 or a 1. If it's a zero, what can you say about the rest of the sequence? What about if it's a one?

Once you piece all this together, you should have a valid recursive definition for your function. As a check, you can try using it to compute $f(4,0)$ since that's a value you already know.