<s>[INST] Probability of not playing an opponent in a contest with $2^n$ players, from Ross Introduction to Probability In a certain contest, the players are of equal skill
and the probability is $\frac{1}{2}$ that a specified one of
the two contestants will be the victor. In a group
of $2^n$ players, the players are paired off against
each other at random. The $2^{n-1}$ winners are again
paired off randomly, and so on, until a single winner
remains. Consider two specified contestants, $A$
and $B$, and define the events $A_i$, $i\leq n$,$E$ by
$A_i$ : $A$ plays in exactly $i$ contests:
$E$: $A$ and $B$ never play each other.
We have to calculate the probability of $P(A_i)$ and $P(E)$.
Though an elegantly simple approach has been stated here
https://math.stackexchange.com/a/2481789/496972 but I wanted to know the flaw in my reasoning
My attempt
$P(A_i)$ is pretty simple. After every elimination round $2^{n-i}$ contestants remain $i=\{0,1,2..n\}$. By symmetry every contestant has an equal chance to make to the $i^{th}$ round. Hence,
$$
P(A_i)= \dfrac{2^{n-i}}{2^n}= \left(\frac{1}{2} \right)^i
$$
If $A$ is eliminated after $i^{th}$ round, he has played  against $i+1$ players. Then the probability of not playing $B$ is same as choosing $i+1$ players out of $2^n- 2$ players. Then,
$$
\begin {align*}
P(E)&= \sum_{i=0}^{n-1} P(E|A_i)P(A_i)\tag{because $A_i$'s are disjoint}\\
&= \sum_{i=0}^{n-1} \dfrac{\binom{2^n-2}{i+1} }{\binom{2^n-1}{i+1}}\times \left(\frac{1}{2} \right)^i\\
&=\sum_{i=0}^{n-1} \dfrac{2^n-2-i}{2^n-1} \times \left(\frac{1}{2} \right)^i\\
&=\dfrac{2^n-2}{2^n-1}\sum_{i=0}^{n-1}\left (\dfrac{1}{2} \right)^i-\frac{1}{2(2^n-1)}\sum_{i=1}^{n-1}i \left(\frac{1}{2} \right)^{i-1}
\end{align*}
$$
When I simplify this expression, it is not remotely close to $1- \dfrac{1}{2^{n-1}}$ which is the answer. Where am I going wrong?
 [/INST] Sorry that I still stick to counting $i$ from $1$ to $n$. This sounds more natural to me.
I think that the calculation is incorrect because
First, in your formula,  $\sum_{i=1}^n P(A_i)=\sum_{i=1}^n \frac {1}{2^i}=1-\frac{1}{2^n} \neq 1 $
It means that something is wrong. Actually $P(A_n)$ should be $\frac {1}{2^{n-1}}$  (See Leander Tilsted Kristensen's comment).
Second, the formula for $P(E|A_i)$ should be $$P(E|A_i)=\frac { 2^n-1 \choose i}{2^n-1 \choose i}=\frac {2^n-1-i}{2^n-1}$$
Accordingly
\begin{align}
P(E) &= \sum_{i=1}^nP(E|A_i)P(A_i) \\
     &= \sum_{i=1}^{n-1}P(E|A_i)P(A_i)+P(E|A_n)P(A_n)  \\   &= \sum_{i=1}^{n-1} \frac {2^n-1-i}{2^n-1}\times \frac{1}{2^i}+ \frac{2^n-1-n}{2^n-1}\times\frac{1}{2^{n-1}} \\
     &= \sum_{i=1}^{n-1}\frac{1}{2^i}-\frac{1}{2^n-1}\sum_{i=1}^{n-1}\frac{i}{2^i}+ \frac{2^n-1-n}{2^n-1}\times\frac{1}{2^{n-1}} \\
     &= 1- \frac{1}{2^{n-1}}
\end{align}
Note:
We can prove that $$-\frac{1}{2^n-1}\sum_{i=1}^{n-1}\frac{i}{2^i}+ \frac{2^n-1-n}{2^n-1}\times\frac{1}{2^{n-1}}=0$$
or equivalently
$$\sum_{i=1}^{n-1}\frac{i}{2^i}=\frac {2^n-1-n}{2^{n-1}}$$
as follows:
Let $$S=\sum_{i=1}^{n-1}\frac{i}{2^i}$$ we have
$$S = \frac{1}{2}+2\left(\frac{1}{2} \right)^2+3\left(\frac{1}{2} \right)^3+ \dots +(n-1)\left(\frac{1}{2} \right)^{n-1} $$
$$\frac{S}{2}= \left(\frac{1}{2} \right)^2+2\left(\frac{1}{2} \right)^3+ \dots +(n-2)\left(\frac{1}{2} \right)^{n-1}+ (n-1)\left(\frac{1}{2} \right)^{n} $$
Hence
$$S-\frac{S}{2}=\frac{1}{2}+\left(\frac{1}{2} \right)^2+ \dots +\left(\frac{1}{2} \right)^{n-1} -
(n-1)\left(\frac{1}{2} \right)^n$$
$$\frac{S}{2}=1-\left(\frac{1}{2} \right)^{n-1}-(n-1)\left(\frac{1}{2} \right)^n$$
$$S=\frac {2^n-1-n}{2^{n-1}}$$
</s>