Expected number of tests in batch testing Suppose we have $n=k^L$ people and we want to test who has a disease. Suppose for each person, the probability of having a disease is $p$. We do the test in batches, first divide these people in $k$ groups each with $k^{L-1}$ people. If the pooled test of a group is positive, we recurse in this group by dividing that group further into $k$ subgroups and continue the process.
What is the expected number of tests needed to pin down the infected individuals? I come up with a recurrence relation but do not know how to solve and simplify. Let $a_n$ be the expected total number of tests. Then we have
$$a_n=k(1-(1-p)^{n/k})a_{n/k}+k$$
How to solve this and simplify the result? How does $a_n$ depend on $k$ and $p$?
 A: Fix an integer $k \ge 2$ and a real number $p\in [0,1]$.

For each positive integer $l$ let
$$
\left\lbrace
\begin{align*}
n(l)&=k^l\\[4pt]
Q(l)&=(1-p)^{n(l)}\\[4pt]
P(l)&=1-Q(l)\\[4pt]
\end{align*}
\right.
$$
and let $e(l)$ be the expected number of tests, assuming

*

*A population of size $n(l)$.$\\[4pt]$

*Each member of the population has probability $p$ of having the disease.

I don't think that a closed form for $e(l)$ can be had.

You proposed a recursion which can be stated as
$$
e(l)
=
\begin{cases}
k+kP(l-1)e(l-1)&&\text{if}\;l > 1\\[4pt]
k&&\text{if}\;l=1\\[4pt]
\end{cases}
$$
but it yields incorrect results for $l > 2$.

A correct recursion can be stated as
$$
e(l)
=
\begin{cases}
{\displaystyle{
k
+
\sum_{h=1}^k
h
\binom{k}{h}
P(l-1)^h
Q(l-1)^{k-h}
e_1(l-1)
}}
&&\text{if}\;l > 1\\[4pt]
k&&\text{if}\;l=1\\[4pt]
\end{cases}
$$
where $e_1$ is defined recursively by
$$
e_1(l)
=
\begin{cases}
{\displaystyle{
k
+
\frac{1}{P(l)}\sum_{h=1}^k
h
\binom{k}{h}
P(l-1)^h
Q(l-1)^{k-h}
e_1(l-1)
}}
&&\text{if}\;l > 1\\[4pt]
k&&\text{if}\;l=1\\[4pt]
\end{cases}
$$
For example, using $k=2$ and applying the above, we get
\begin{align*}
e(1)&=2\\[4pt]
e(2)&=-4p^2+8p+2\\[4pt]
e(3)&=-4p^4+16p^3-32p^2+32p+2\\[4pt]
\end{align*}
As a numerical example, using $k=2$ and $p={\large{\frac{1}{10}}}$, we get
$$
e(3)=\frac{12239}{2500}\approx 4.90
$$
which agrees with results obtained from a simulation.
