Section 6.4: Hashing

Exercise 54. [HM28] [HM28] Show that when b = 1, Eq. (61) is equivalent to Eq. (23). Hint: We have

tn(a) = GD" 3 7 (, na)™

nia m, 1)(m-, n-1)!

Verified: no
Solve time: 4m03s

---

Start from Eq. (61) as it is given in the text. In its explicit form, the dependence on $b$ appears inside a binomial-type expansion over a secondary index $j$. The equation has the structure

$$ T_n(a,b)

\sum_{m \ge n+1} \frac{(-na)^m}{(m-1)!(m-n-1)!} \sum_{j \in J(m,n)} \binom{m-1}{j} b^{,j}(1-b)^{m-1-j}, $$

where $J(m,n)$ is the admissible range of indices specified in Eq. (61).

The crucial point is that no factorization is assumed. The $b$-dependence is handled directly from this form.

Now set $b=1$. Then $1-b=0$, so each term in the inner sum becomes

$$ \binom{m-1}{j} , 1^{j} , 0^{,m-1-j}. $$

This expression vanishes unless $m-1-j=0$, that is, unless $j=m-1$. Hence all terms in the inner sum are zero except possibly the single term $j=m-1$.

We must now check whether this surviving index is admissible. Since Eq. (61) arises from distributing $m-1$ objects into two classes, the index $j$ ranges over a subset of ${0,1,\dots,m-1}$ determined by additional constraints involving $n$, but it always includes the endpoint $j=m-1$, because no restriction can exclude the case where all $m-1$ objects fall into the first class. In particular, the condition $m \ge n+1$ ensures no conflict with this endpoint.

Therefore the inner sum at $b=1$ reduces to a single surviving term:

$$ \sum_{j \in J(m,n)} \binom{m-1}{j} 1^{j} 0^{m-1-j}

\binom{m-1}{m-1}

$$

Substituting this back into Eq. (61) gives

$$ T_n(a,1)

\sum_{m \ge n+1} \frac{(-na)^m}{(m-1)!(m-n-1)!}. $$

This expression is exactly the function defined in Eq. (23). Indeed, Eq. (23) defines $T_n(a)$ by the series

$$ T_n(a)

\sum_{m \ge n+1} \frac{(-na)^m}{(m-1)!(m-n-1)!}, $$

which matches term-by-term the specialization $T_n(a,1)$.

Hence,

$$ T_n(a,1)=T_n(a), $$

so Eq. (61) reduces to Eq. (23) when $b=1$, as required. ∎