The other day on the Mathematics StackExchange, I came across a question about a closed form solution for a certain set of battle mechanics. The problem intrigued me and I found some interesting results. Here's some of what I found.
The battle mechanics are as follows. For battling armies $X$ and $Y$, a battle consists of rounds of (what I will call) conflicts. Each conflict is a $1$ on $1$ interaction between a member of $X$ and a member of $Y$ with an equal chance of victory for both sides. The loser of a conflict is "dead" and the winner can compete in the next conflict. The last army with men is the victor.
It turns out that it's possible to quickly compute the probable outcome. Let $P(x,y)$ be the probably that a battle, between army $X$ with $x$ men and army $Y$ with $y$ men, results in a victory for army $X$. The battle mechanics can be summarized in three rules:
$$P(x,0) = 1$$
$$P(0,y) = 0$$
$$P(x,y) = \frac{1}{2}(x,y-1) + \frac{1}{2}P(x-1,y)$$
The first two rules are pretty self explanatory; if army $Y$ has no men, army $X$ wins and visa versa. The third can be understood by looking at a conflict. A conflict has two results: army $X$ wins or army $Y$ wins. If army $X$ wins, then army $Y$ loses a man and the rest of the battle has the same odds as a battle of two armies of size $x$ and $y-1$, respectively (fatigue isn't considered, so the member of army $X$ in the first conflict is indistinguishable from any other member of army $X$ after that first conflict). Likewise a conflict win for army $Y$ results in the rest of the battle to have the odds as that of two armies of size $x-1$ and $y$. And since we have equal odds, there's a $50\%$ chance of the former and a $50\%$ chance of the latter.
I will show that
$$P(x,y)=\frac{1}{2^{x+y-1}}\sum_{i=0}^{n-1}\dbinom{x+y-1}{i}$$
To start, let's start with armies of size $x$ and $y$ and start expanding with our third rule. Each of the below are equivalent.
$$\frac{1}{1}\left[P(x,y)\right]$$
$$\frac{1}{2}\left[P(x,y-1) + P(x-1,y)\right]$$
$$\frac{1}{4}\left[P(x,y-2) + 2P(x-1,y-1)+P(x-2,y)\right]$$
Let's stop here and explain what we're doing. From the first line to the second is pretty obvious, we just invoked our rule and pulled out the common factor of $1/2$. The progression from the second line to the third line invokes the rule twice (one for each of the evaluations of $P$). The left
$$P(x,y-1)=\frac{1}{2}\left[P(x,y-2)+P(x-1,y-1)\right]$$ and the right $$P(x-1,y)=\frac{1}{2}\left[P(x-1,y-1)+P(x-2,y)\right]$$
Putting them together involved pulling out the common factor of $1/2$ (and combining this with the already factored out $1/2$) and then combining both terms of the form $P(x-1,y-1)$. Let's proceed with the expansion, but for the sake of space, We will denote $P(x-a,y-b)=P_{a,b}$
$$\frac{1}{8}\left[P_{0,3} + 3P_{1,2}+3P_{2,1}+P_{3,0}\right]$$
$$\frac{1}{16}\left[P_{0,4} + 4P_{1,3}+6P_{2,2}+4P_{3,1}+P_{4,0}\right]$$
And by now, it should be strikingly apparent that the coefficient are rows of Pascals triangle and we can rewrite $P(x,y)$ as
$$P(x,y)=\frac{1}{2^j}\sum_{i=0}^j\dbinom{j}{i}P(x-i,y-j+i)$$
where $j$ is the number of conflicts so far. However, there is a bound on the number of conflicts. For instance, the battle can't be over until at least $\min(x,y)$ conflicts have taken place (otherwise, no one is out of men). And as an upper bound, no more than $x+y-1$ conflicts can happen. If $x+y$ conflicts take place, then a total of $x+y$ men are dead and both armies are dead. Therefore, we take one less conflict and this lone man is the victor! With this upper bound, we can write
$$\begin{align*}P(x,y)=&\frac{1}{2^{x+y-1}}\sum_{i=0}^{x+y-1}\dbinom{x+y-1}{i}P(x-i,y-(x+y-1)+i)\\
&=\frac{1}{2^{x+y-1}}\sum_{i=0}^{x+y-1}\dbinom{x+y-1}{i}P(x-i,1+i-x)\end{align*}$$
However, for all $i\geq x$ we have $P(0,1+i-x)=0$ so we can ignore any $i\geq x$.
$$P(x,y)=\frac{1}{2^{x+y-1}}\sum_{i=0}^{x-1}\dbinom{x+y-1}{i}P(x-i,1+i-x)$$
However, we can see the for $i\leq x-1$, we have $P(x-i,0)=1$. Therefore we have removed the dependency on $P$ on the RHS.
$$P(x,y)=\frac{1}{2^{x+y-1}}\sum_{i=0}^{x-1}\dbinom{x+y-1}{i}$$
We have shown what I've wanted to show here. This equation, in words, is the probability that army $X$ with $x$ soldiers wins over army $Y$ with $y$ soldiers is the sum of the first $x$ elements in the $(x+y-1)$th row of Pascal's triangle divided by the total sum of the $(x+y-1)$th row of Pascal's triangle! I will discuss the properties and shortcuts to this equation in the next part. Just as a preview:
$$P(x,x) = \frac{1}{2}$$
$$P(x,y) + P(y,x) = 1$$
$$P(x,1) = \frac{2^x-1}{2^x}$$
$$P(x,2) = \frac{2^{x+1}-x-2}{2^{x+1}}$$
$$P(x,3) = \frac{2^{x+3}-x^2-5x-8}{2^{x+3}}$$
