This is my question, and I don't know how to approach it.
$R$ is a binary relation on set $S$. $R_0$, $R_1$, $R_2$…. are defined as below:
$R_0 := I = \{(x,x) : x ∈ S\}$
$R_{n+1} := R_n ∪ (R;R_n)$ for $n >= 0$
There exists $i ∈ N$ such that $R_i = R_{i+1}$
If |S| = u, show that $R_{u^2} = R_{u^2 + 1}$ and explain the reason.
HINT: $\langle a,b\rangle\in R_n$ if and only if there are $a_0=a,a_1,\ldots,a_n=b\in S$ such that $\langle a_k,a_{k+1}\rangle\in R$ for $k=0,\ldots,n-1$. If $n>u^2$, the pigeonhole principle says that there are distinct $k,\ell$ such that $\langle a_k,a_{k+1}\rangle=\langle a_\ell,a_{\ell+1}\rangle$.