I'm currently reading a paper "On the foundations of machine learning" by F.Cucker and S.Smale and I got stuck on an apparently simple problem.
In order to prove an inequality that gives bound on covering number of finite dimensional Banach space authors introduced two numbers:
Let $S$ be a metric space. For $k\geq1$ define:
$ \varepsilon_{k}(S) = \inf \left\lbrace \varepsilon >0 : \exists \text{ closed balls $D_{1}, \dots, D_{k}$ with radius $\varepsilon$ covering S}\right\rbrace $
$ \varphi_{k}(S) =\sup \left\lbrace \delta>0 : \exists \; x_{1}, ..., x_{k+1} \in S \text{ such that for $i \neq j$, $d(x_{i}, x_{j})>2\delta$} \right\rbrace $
And then, they wrote down a Lemma:
For all $ k \geq 1$, $\varphi_{k}(S) \leq \varepsilon_{k}(S) \leq 2\varphi_{k}(S)$.
The proof of this lemma is shrinked down to the statement "it's easy to prove", but unfortunately I failed to do so. I would appreciate any help or hint.
Also, it's my first exposure to covering numbers and I do not even know what are the names of numbers defined above so I have troubles finding useful resources on this topic.
To show $\varphi_k(S) \le \varepsilon_k(S)$, suppose $\varepsilon > 0$ is such that there are closed balls $D_1, \dots, D_k$ of radius $\varepsilon$ that cover $S$. Now suppose that $x_1, \dots, x_{k+1}$ are any $k+1$ points in $S$. By the pigeonhole principle, two of those points must be contained in one of the $D_i$, so by the triangle inequality the distance between those two points is less than $2\varepsilon$. Therefore, there do not exist $k+1$ points with pairwise distances greater than $2\varepsilon$, so $\varphi_k(S) \le \varepsilon$. Taking the infimum over all such $\varepsilon$ shows $\varphi_k(S) \le \varepsilon_k(S)$.
For the second inequality, suppose $\varepsilon < \varepsilon_k(S)$. That means that one cannot cover $S$ with $k$ balls of radius $\varepsilon$. So construct a sequence of points $x_1, \dots, x_{k+1}$ as follows. Choose $x_1 \in S$ arbitrarily. Then recursively, if $n \le k$ and $x_1, \dots, x_n$ have already been chosen, by assumption the balls $B(x_i, \varepsilon)$, $i=1,\dots, n$, do not cover $S$, so we can choose $x_{n+1} \in S \setminus \left(\bigcup_{i=1}^n B(X_i, \varepsilon)\right)$. This construction produces $k+1$ points with pairwise distances at least $\varepsilon$, so $\varphi_k(S) \ge \varepsilon/2$, or in other words $2 \varphi_k(S) \ge \varepsilon$. Now let $\varepsilon \uparrow \varepsilon_k(S)$ to get the result.