We will use without a proof the following claim that appears in the "Weighted quick-union analysis" of section "1.5 CASE STUDY: UNION-FIND" of the book.
Claim of (strong) worst case: the worst case for weighted quick-union happens when the sizes of the trees to be merged by union() are always equal (and a power of 2).
Define tree $W_n$ recursively. $W_0$ is the tree with one node whose component root is itself. $W_{n+1}$ is the tree obtained by combining two $W_n$ using the union procedure. According to the above claim, a worse case is $W_n$ for some $n$. Let $D(T)$ be the average depth of a node in a rooted tree $T$.
(Structure of $W_n$) $W_n$ has $2^n$ nodes in total and $\binom ni$ nodes at level $i$ for $0\le i\le n$. $D(W_n)=n/2$.
Proof. The base case when $n=0$ and $n=1$ is easy.
Suppose it is true when $n=k$. $W_{k+1}$ is the join of two $W_{k}$. WLOG, let us say one of them is at the left and its root is selected as the root of $W_{k+1}$ during the join. Note that depths of all nodes in the left $W_k$ remains the same after the join while depths of all nodes in the right $W_k$ are increased by 1 after the join. So, $$ D(W_{k+1})=\frac12 D(W_k) + \frac12 (D(W_k)+1) = \frac12(\frac k2+(\frac k2 +1))= \frac {k+1}2$$ $W_{k+1}$ has one root at level 0 and one node at level $k+1$, which was the unique node at level $k$ of the right $W_k$. The nodes in $W_{k+1}$ at level $i$ come from the nodes in the left $W_k$ at level $i$ and the nodes in the right $W_k$ at level $i-1$, so the number of them is $$\binom ki+\binom k{i-1}=\binom {k+1}i,$$ for all $0<i\le k$. Proof is done.
For completeness, let us define a reasonable version of worst cases. As the above, let $D(T)$ be the average depth of a node in a rooted tree $T$. Let $I$ be a quick-find implementation of the union-find data structure, such as (naive) quick-find or weighted quick-find.
A definition of general worst cases. Given implementation $I$, the worst case of $I$ with $k$ nodes is a rooted tree $T$ with $k$ nodes such that the average depth of nodes in $T$ is the largest among all trees obtained by $I$ on $k$ nodes.
Let us define $\mathcal W_k$ recursively as follows. $\mathcal W_0$ is the rooted tree with a single node. $\mathcal W_{2^n+m}$ is the tree obtained by combining $\mathcal W_{2^n}$ and $\mathcal W_m$ using the weighted union procedure, for $n\ge0$ and $1\le m\le 2^n$.
(Another version of exercise 1.5.15) Show that any worst case of weighted quick-union is $\mathcal W_{k}$ for some $k$. Compute $D(\mathcal W_{2^n})$.
(Sameness of worst cases) Let $\mathcal A_k$ be the tree obtained by weight quick-union on $k$ nodes using the most accesses. Show that $\mathcal A_k$ is the same as $\mathcal W_k$.
