I am trying to answer the math.stackexchange question found here by developing all the theory from scratch and not using Bertrand's ballot theorem. My logic boils down to being able to prove the following identity:
$$ \frac{n-m+1}{n+1} \binom{n+m}{n} = \frac{n-m}{n} \binom{n+m-1}{n-1} + \frac{n-m+2}{n+1} \binom{n+m-1}{n}$$
where $0 < m < n$.
I tried using Wolfram but not an expert (or a subscriber). I thought of multiplying both sides to clear the denominator and see what happens, but it seems a bit daunting.
So I post the problem here hoping that 'cranking it out' doesn't involve too many algebraic/binomial tricks of the trade.
Well, we just need to simplify the right hand side:
\begin{align} RHS &= \frac{n-1-m+1}{n} {n+m-1 \choose n-1} + \frac{n-m+2}{n+1} {n+m-1 \choose n} \\ &= \frac{n-m}{n} \frac{(n+m-1) !}{(n-1)! m!} + \frac{n-m+2}{n+1} \frac{(n+m-1) !}{n! (m-1)!} \\ &= \Big[\frac{n-m}{n+m} + \frac{(n-m+2)m}{(n+1)(n+m)}\Big] {n+m \choose n} \end{align}
So now we just need to show the following equality: $$ \frac{n-m+1}{n+1} = \frac{n-m}{n+m} + \frac{(n-m+2)m}{(n+1)(n+m)}$$
The right hand side can be written as:
\begin{align} \frac{n-m}{n+m} + \frac{(n-m+2)m}{(n+1)(n+m)} &= \frac{(n-m)(n+1) + (n-m+2)m}{(n+m)(n+1)} \\ &= \frac{n^2+n+m-m^2}{(n+m)(n+1)}\\ &= \frac{(n+m)(n-m+1)}{(n+m)(n+1)}\\ &= \frac{n-m+1}{n+1}\\ \end{align}
Which gives you the result.