2

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.

DDS
  • 3,199
  • 1
  • 8
  • 31
Charlotte
  • 1,674
  • 1
    Since $r\geq u\geq0$, the basis should be $r=u=0$. – saulspatz Jul 12 '19 at 12:25
  • @saulspatz;is it wrong to take $n=1?$ and then take $r=1,u=0$? – Charlotte Jul 12 '19 at 12:27
  • 1
    Yes. The statement is supposed to be true for $r\geq u \geq 0.$ That means you have to prove it in the case $r=u=0$ also. Start from $n=0.$ That being said, the statement doesn't seem to be true as written. If $r=2, u=1$ it gives $2$, but there are $3$ ways to count the votes: $rru,, rur,, urr.$ The answer should be ${r+u,\choose r}$. Have you left something out? Perhaps $r$ should never be behind in the counting? – saulspatz Jul 12 '19 at 12:33
  • 1
    Yes, that's it. See https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem#Variant:_ties_allowed – saulspatz Jul 12 '19 at 12:36
  • @saulspatz;so i guess the expression is correct – Charlotte Jul 12 '19 at 12:47
  • @saulspatz;can you give a proof by induction – Charlotte Jul 12 '19 at 12:48
  • Look at the the link I gave you. There's a proof by induction for the original version given there. Try to adapt it to the non-tie case. – saulspatz Jul 12 '19 at 12:50
  • @Abr001am I don't understand what you are saying that is different from what I said. – saulspatz Aug 19 '19 at 15:00
  • Math_Freak for r=u=1 there is 2 ways of counting, while the theorem gives out 1 way, you should precise that r should always be in advance like @saulspatz have quite said. – Abr001am Aug 19 '19 at 17:26

2 Answers2

0

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 $$

robjohn
  • 345,667
0

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.

Abr001am
  • 746