Raney’s Lemma

Raney’s Lemma: Given an integer sequence $(a_0, a_1, \dots, a_{m-1})$ whose sum equals unity, there exists a unique $j$ such that every partial sum of the sequence $(a_j, a_{j+1}, \dots, a_{j+m-1})$ is positive, indicies being computed $\mod m$ .

The standard proof for this fact is geometric. It starts by extending the above sequence to an infinite periodic sequence, $b_n$ , for all non-negative integers such that $b_p = a_q$ , whenever $p \equiv q \mod m$ . Since the new sequence of partial sums obeys $s_{km+n}=k+s_n$ , where $0 \le n < m$ , the plot of $s_n$ for $n \ge 0$ has an average slope of $\frac{1}{m}$ . In fact, the sequence $s_n$ can be completely contained within two lines of slope $\frac{1}{m}$ . But lines of slope $\frac{1}{m}$ meet integer points only once every $m$ units. Thus, the lower line meets the integer partial sum sequence exactly once in the canonical period $0 \le n < m$ , which is the required point $(j, s_j)$ .

The above lemma, sometimes also called the Cycle Lemma, immediately solves the following problem: How many sequences of length $2n+1$ consisting only of $+1$ s and $-1$ s and summing to unity have all positive partial sums? A straightforward generalization of the above enumeration problem asks us to count the number of $m$ -Raney sequences: How many sequences of length $mn+1$ consisting only of $+1$ s and $(1-m)$ s and summing to unity have all positive partial sums?