TAOCP 2.3 Exercise 7
Let $A$ be the nearest common ancestor of $X$ and $Y$.
Exercise 7. [**] [23] Extend the definition given in the previous exercise to all $m \ge -1$ and to all integers $n \ge -(m + 1)$ in such a way that for any two nodes X and Y of a tree there are unique $m$ and $n$ such that X is an $m$th cousin of Y, $n$ times removed.
Verified: no
Solve time: 33s
Let $A$ be the nearest common ancestor of $X$ and $Y$. Let the distances from $A$ to $X$ and $Y$ be $r$ and $s$, respectively. Without loss of generality, assume $r \ge s$.
Define
$$ m=s-1,\qquad n=r-s. $$
Then $m\ge -1$ and $n\ge 0\ge -(m+1)$. We say that $X$ is an $m$th cousin of $Y$, $n$ times removed. When $s=0$, we have $m=-1$; thus the cases $m=-1$ describe ancestor-descendant relationships. When $s=1$, we have $m=0$; thus siblings are $0$th cousins. For $s\ge2$, this agrees with the usual definition that nodes whose nearest common ancestor is $s$ levels above the nearer node are $(s-1)$st cousins, and the difference in depths below that ancestor is the number of removals.
For any pair of nodes $X$ and $Y$, the nearest common ancestor $A$ is unique, and the distances $r$ and $s$ are uniquely determined. Hence
$$ m=s-1,\qquad n=r-s $$
are unique. Conversely, given $m$ and $n$, we recover
$$ s=m+1,\qquad r=m+1+n, $$
so the pair $(m,n)$ is uniquely determined by the relative positions of $X$ and $Y$. Therefore for any two nodes there exist unique integers $m\ge -1$ and $n\ge -(m+1)$ such that $X$ is an $m$th cousin of $Y$, $n$ times removed.
This completes the proof.
∎