Counting the Number of Votes by Induction

Question

Suppose that $A$ has $r$ votes and $B$ has $u$ votes where $r\ge u\ge 0$. Show by induction that the number of ways to count $n=r+u$ votes is

$\frac{r-u+1}{r+1}\binom{r+u}{r}$.

I verified the case for $n=1$ by taking $r=1,u=0$ but I can't prove the general case.

How may I show this using induction. Please help.

Answer 1

In equation $(10)$ of this answer, it is shown that $$ b_{s,n}=\frac{s+1}{\frac{n+s}2+1}\binom{n}{\frac{n+s}2}\,[2\mid n+s]\tag1 $$ where $b_{s,n}$ is the number of strings of $+1$ and $-1$ of length $n$ with non-negative partial sums that total to $s$. However, that answer, and the answer it is based on, use generating functions and induction.

Plugging in $n=r+u$ and $s=r-u$, we get $$ \frac{r-u+1}{r+1}\binom{r+u}{r}\tag2 $$

Answer 2

From my, and anyone's first impression given by the question syntax in it's standing form, one may starts to count the number of combinations of votes with all $n$ ballots unfolded, like in case $r=2,u=1$ the ordering $rru$ is discarded because whatever the value hidden in the last ballot, counting it won't be necessary, unfortunately it's just Bertrand's ballot problem with ties variant. Hope the author clears this up.

It's appearent near the cases $r=u$ where the subcase $r=0$ and $n=r$ the formula responds well to this problematic, remaining to prove for $n=r+u$ given the hypothesis is true for $r-1,u$ and $r,u-1$ where $u<=r$ and $A$ has the last vote for case (1) and $B$ votes last in case(2).

From the following arbitrary views for case(1):$\underbrace{rrururr...}_{T_{u,r-1}}\color{red}r$ and case(2):$\underbrace{rurrrru...}_{T_{u-1,r}}\color{red}u$ the ordering of votes $T$ doesn't interleave with the last vote $u$ or $r$ which means that the final sum of combinations is just $T*1$ which says $T_{r\ is\ last}\cup T_{u\ is\ last}$ is just $|T_{u,r-1}|*1+|T_{u-1,r}|*1$ because $T_{r\ is\ last}\cap T_{u\ is\ last}$ is empty.

Since $\frac{r-u+1}{r+1}\binom{r+u}{r}$ can be expressed like $\binom{r+u}{r}-\binom{r+u}{r-1}$ for $S=|T_{u,r-1}|+|T_{u-1,r}|$ to be true means $S=\color{red}{\binom{r-1+u}{r-1}}-\color{blue}{\binom{r-1+u}{r-2}}+\color{red}{\binom{r+u-1}{r}}-\color{blue}{\binom{r+u-1}{r-1}}$ Summing up the same colored entities using pascal's rule gives $$S=\color{red}{\binom{r+u}{r}}-\color{blue}{\binom{r+u}{r-1}} $$ ie: what to be proven.