Intuitive proof for Floyd's cycle detection algorithm
By definition, $x_0,\ldots,x_{\mu+\lambda-1}$ are all distinct, and for $i \geq \mu$, we have $x_{i+\lambda} = x_i$. Now let us prove the claim:


  Let $i \geq 1$. Then $x_i = x_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.


$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu$, we have $x_{i+t\lambda} = x_i$ for all $t \geq 0$. In particular, choosing $t := k$, we get $x_{2i} = x_{i+k\lambda} = x_i$.

$\Longrightarrow$ Suppose that $x_i = x_{2i}$. If $i &lt; \mu$ then $x_j = x_i$ if and only if $j = i$. Since $2i \neq i$ (as $i \neq 0$), this contradicts the assumption $x_i = x_{2i}$, showing that $i \geq \mu$.

Since $i \geq \mu$, $x_i = x_{\mu + [(i-\mu) \bmod \lambda]}$. Similarly, $x_{2i} = x_{\mu + [(2i-\mu) \bmod \lambda]}$. Since $x_\mu,\ldots,x_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda$, and so $i$ is a multiple of $\lambda$.