Very nice work Shmoe. I think I can understand why it goes to infinity now. I had been totally mystified. You did say that you had no proof of f(n,0)=C^{n}_{floor(n/2)}.
I think I may be able to supply that, if I really got it straight.
Also, by your inequality: E(n)=f(n-1,0)/2^n+E(n-1) we need only consider the infinite subset containg elements of even or odd order since we have: E(2n+1)>E(2n)>E(2n-1)>E(2n-2)>...This is a nice simplification.
Let us then consider a "truth table" series of Xs and 1s, that is an orderly array containing 2n elements, r of which are X and 2n-r of which are 1. These are then arranged in binominal series: 2nC0, 2nC1...2nC2n since of the 2n elements giving us 2n! arrangements, r are the same and 2n-r are the same giving us (2n!)/(r!(2n-r)!) ways of arranging this array.
In this case we have the rule that we never walk backward if we are at the wall, so that at that position adding another X leaves us where we are. But the 1s always accumulate and the steps can be "knocked back" by adding on a X. That is, k+X = k-1, unless k=0 and then 0+X = 0. Examples: XX11=2, X1X1=1.
The insight we need is that we check along the lines of the array to see if the 1s predominate along the line to the right from some certain point, say if we are dealing with 14C7, in the line: 11XX11XXX1XX11=2, when we read up to (XXX)1XX11 we see that now we are going to have more 1s than Xs remaining and so since the 1s accumulate, the Xs are unable to make the line equal 0. (The nice part about this is that we really don't care if the arrangement is ...1XX11=2, or ...1X1X1=1, we just know the sum is not zero.)
Thus as we look at the binominal series: 2nC0, 2nC1...2nCn...2nC2n, we see that no sums are going to add to a zero prior to the middle term: 2nCn because it is first time the Xs are as great as the 1s.
It might be said that in this particular case, 2nCn, for the 0s we are looking at a Catalan number which can be interpreted as a voting situation where one side is never behind in the count. Why? Because if the Xs predominate, even from the very first: X... then looking down the line past that first X, we see there will be more 1s coming up than Xs and so the sum will not be 0. I mention the reference:
http://en.wikipedia.org/wiki/Catalan_number and refer you to the counting argument of D Andre.
Looking at the counting argument of D Andre in more detail: In the case of 6N3 where we have the line X1X1X1=1 looking past the first X, which means the sum will be 1 or more, we reverse the remaining elements producing: XX1X1X. This is an element from the set: 6N4. Now any element is the set 6N4 will always have an excess of Xs and past the first time it occurs, which is at the X, we reverse all the elements following and get the number X1X1X1=1. Thus every element from 6N4 can be "reversed" and transformed into an element in the set 6N3, which sums to 1 or more. Two examples from the set 6N4 are: XXXX11 and 11XXXX, these "reverse" and give X111XX=1, and 11XXX1=1.
Thus the counting argument says that the number of 0 sums in the array of \frac{2n!}{n!n!} elements containing nXs and n1s is
[ \frac{2n!}{n!n!}-\frac{2n!}{(n+1)!(n-1)!}]
When we move along to the term 2nC(n+1), where the Xs predominate, to get at the 1s that will come out of the array, we have to go past the first two Xs that predominates and add one more of them giving three excess, the 1s will then predominate on the line, and the reasoning is the same as before giving the 0s as 2nC(n+1)-2nC(n+2). For example: XXXX11 is transformed into XXX1XX. Note too, that we do not care if instead of XXXX11=2, we had the case to handle of XXX11X=1, which transforms into XXXXX1, another member of the same set, namely: 2nC(n+2). Also, cases like 11XXXX =0, never present us with three excessive Xs, so they are not eligable to be transformed, which is correct since the value is 0. Going in reverse we look at the case of X1XXXX, transforming into X1XXX1=1. Or for that matter, we could have looked at XXXXX1, transforming into XXX11X=1.
When we reach 2nC(2n-1), we can continue the argument above or clearly see that only one 1 is present in each line of the array, and so only XXXXX...XX1=1. This is again the same form: 2nC(2n-1) - 2nC2n. At the final case 2nC2n, there is only Xs and so there is only one arrangement and in this case we have 2nC2n =1.
Stringing everything together we get [2nCn-2nC(n+1]+[2nC(n+1)-2nC(n+2)]+++[2nC(2n-1)-2nC2n] + 2nC2n =2nCn, which is exactly what Schmoe conjectured.
My bad...completely ignore my previous post.
