# I do not understand the result of 'proposition 2' of "MDx-MAC and building fast MACs from hash functions"

I saw the difference between the proof and the statement of "proposition 2" in the paper "MDx-MAC and building fast MACs from hash functions" by Bart Preneel & Paul C. van Oorschot. Is there anyone understanding the term $$2^m / (2^m - 1)$$ in its proof?

This is their proposition:

Let $$h$$ be an iterated MAC with $$n$$-bit chaining variable and $$m$$-bit result. An internal collision for $$h$$ can be found using u known text-MAC pairs and v chosen texts. The expected values for u and v are as follows: $$u = \sqrt{2} \cdot 2^{n / 2}$$ and $$v = 0$$ if the output transformation $$g$$ is a permutation; otherwise, $$v$$ is approximately $$2 \cdot 2^{n-m} + 2 \lceil{n/m}\rceil$$.

And this is their proof:

If the number of known texts is $$r = \sqrt{2} \cdot 2^{n/2}$$, a single internal collision is expected by the birthday paradox (note $$\begin{pmatrix} {r \\ 2}\end{pmatrix} / 2^n \approx 1$$). If $$g$$ is a permutation (e.g. the identity mapping), all collisions are internal and the results follows by Lemma 1. If $$g$$ behaves as a random function, $$\begin{pmatrix} {r \\ 2}\end{pmatrix} / 2^m \approx r ^2/2^{m+1} = 2^{n−m}$$ external collisions are expected and additional work is required – for a verifiable forgery – to distinguish the internal collision from the external collisions. (Note Lemma 1 requires internal collisions.) This may be done by appending a string y to both elements of each collision pair and checking whether the corresponding MACs are equal. This requires $$2(1 + 2^{n−m})$$ chosen text-MAC requests. For an internal collision both results will always be equal, while for an external collision this will be so with probability $$1/{2^m}$$. Discard collision pairs corresponding to unequal MACs. The expected number of remaining collision pairs after this stage is $$2^{n−2m}$$ external plus one internal (but these cannot yet be distinguished). If the (total) number of remaining collision pairs is 2 or more (e.g. $$n − 2m > 0$$), further external collisions must be discarded by appending a different $$y$$, and continuing in this manner until only a single collision remains; with high probability this is an internal collision. This may require a small number of additional chosen texts and a total number $$2 \cdot 2^{n−m} \cdot 2^m/(2^m − 1) + 2 \lceil{n/m}\rceil$$

I really do not understand their conclusion because of the term $$2^m/(2^m - 1)$$.