# Finding Recurrence Relation of Number of Sequences of $+1$'s and $-1$'s that Sum to Zero and Have Non-Negative Partial Sums

Question: Find a recurrence for the number $h_n$ of sequences of length $2n$ of $+1$'s and $-1$'s such that: every partial sum is non-negative, and the entire sum is zero.

I tried to consider the possible last two entries of the sequence and consider them separately. There are four possibilities, the sequence ends in $-1$,$-1$ or $+1$,$+1$ or $-1$,$+1$ or $+1$,$-1$. For each, this necessarily means, to ensure that the entire sum is zero, that there must be two $1$'s of the exact opposite sign that came before. So we must choose where those two opposite singed $1$'s go. For example, for the sequence ending in $-1$,$-1$, there must be two $+1$'s somewhere in the first $2n-2$ positions, and the rest reduces down to $h_{n-4}$, so we have ${{2n-2} \choose 2} \cdot h_{n-4}$ sequences that end in $-1$,$-1$. I am unsure how to do the other 3 cases, mainly because there will at least be a $-1$ that i need to put in the previous entries, and I cannot just put it anywhere because the partial sums might not all be non-negative. In the previous case that I did, I am free to choose wherever to put the $+1$'s because they will not make any partial some negative. I am unsure if all this is the right approach. Help is appreciated.

• This is one characterization of the Catalan Numbers – lulu Jul 17 '17 at 20:39
• Your sequence cannot end in $+1$ because the sum before that would be $-1$ – Ross Millikan Jul 17 '17 at 20:54

Consider the first time $2k$ for $k > 0$ for which the partial sum is equal to $0$. This gives a first sequence of length $2k$ and a last sequence of length $2n - 2k$ too. Both of these sequences must start with $+1$ and end with $-1$, so if we remove these, we get a sequence of length $2k-2$ and $2n - 2k - 2$ that both satisfy the same condition. This implies that $$h_{n+1} = \sum_{k=0}^n h_k h_{n-k}.$$