Prove one set is a convex hull of another set Define two sets:


*

*$A = \{x \in \{0,1\}^n : \lVert x \rVert_1 \leq k\}$ is a finite set of binary vectors;

*$B = \{x \in [0,1]^n : \lVert x \rVert_1 \leq k\}$ is an infinite set of real-valued vectors, whose elements are between $0$ and $1$;


where $0 \leq k \leq n$, $k$ is an integer and $\lVert x \rVert_1$ denotes the $l_1$ norm: $\lVert x \rVert_1 = \sum_{i=1}^{n} \lvert x_i \rvert$.
I believe $B$ is the convex hull of $A$ ($conv(A)$), but cannot prove it. It is easy to show $conv(A) \subseteq B$. I'm stuck at the reverse direction. I'm thinking of using induction proof: assume it holds for $0 \leq k < n$, prove that it also holds for $k+1$; but I haven't succeeded.
 A: $B = B_1 \cup B_2$
where 
$$B_1 = \{x \in [0,1]^n : \lVert x \rVert_1 = k\}$$
and 
$$B_2 = \{x \in [0,1]^n : \lVert x \rVert_1 < k\}$$
Let $x \in B$
Cas 1: $x \in B_1$
lets write x in its cartesien representation ($(e_i)i$ is the trivial base of the orthonormal space $\mathbb{R}^n$ and $(x_i)i$ the cordianates of x in this base)
$x=\sum_{k=1}^{n}{x_i.ei}$
$x=\sum_{k=1}^{n}{\frac{x_i}{k}*k.ei}$
we have all the vectors $k.e_i \in A$
and we have
$\sum_{k=1}^{n}\frac{x_i}{k}=1$ and all $\frac{x_i}{k} \geq 0$
so $x \in conv(A)$
$$B_1 \subset conv(A)$$
Cas 2: $x \in B_2$
suppose $x\neq O$
if we can find y such that $x=\lambda.y+(1-\lambda).O = \lambda.y$ and $y \in B_1$ and $\lambda \in [0,1]$. 
then we can conclude that  $x \in conv(A)$
that $y$ is $y=\frac{k}{\lVert x \rVert_1}x$ and $\lambda = \frac{\lVert x \rVert_1}{k}$
$$B_2 \subset conv(A)$$
then $$B \subset conv(A)$$
to summerize


*

*B is convex (its the intersection of Ball (O,k) and the positive Orthant, both convex sets)

*$conv(A)$ is the smallest convex that contain A

*$A \subset B$

*$B \subset conv(A)$


we can conclude that $$B = conv(A)$$
A: I think there are probably a variety of proofs with lengths depending on the amount of polyhedral theory you want to invoke.  Here is one method: show that all extreme points of $B$ are in $A$.  This suffices by compactness of $B$.
Let $x$ be an extreme point of $B$.  The set $B$ is defined by $2n + 1$ linear inequalities: $0\leq x_i\leq 1$ and $\sum x_i \leq k$.  At an extreme point $n$ of these constraints must be tight (hold with equality).  For each $x_i$ at most one of the bound constraints $0\leq x_i$ or $x_i\leq 1$ can be tight.
Suppose $x\not\in A$. There is some $j$ without a tight bound constraint: $x_j\in (0,1)$.  Given that, the only way to have $n$ inequalities tight at $x$ is to have $\sum x_i = k$ and also have each $x_i$ with $i\neq j$ satisfy some bound constraint.  But then $x_j = k - \sum_{i\neq j} x_i$ is an integer, a contradiction.
A: It is true that $\mathbb{co} A = B$, but the proof is a little tedious.
Since $A \subset B$, it is clear that $\mathbb{co} A \subset B$. The other direction requires a little more work: 
Both $A$ and $B$ are closed bounded sets, hence compact. $B$ is convex. The convex hull $\mathbb{co} A$ is closed and compact (follows from compactness and Carathéodory's theorem).
Let $E$ be the set of extreme points of $B$. The basic idea is to show that $E \subset A$. Since the Krein-Milman theorem tells us that $B = \overline{\mathbb{co}} E$, it then will follow that $B \subset \mathbb{co} A$.
To characterize the extreme points, I need some notation and a lemma.
Let $C = \{ x \in \mathbb{R}^n | \; g_i (x) \leq 0, \; \forall i \in I \}$, where each $g_i$ has the form $g_i(x) = \langle \gamma_i, x \rangle - \beta_i$. (Note that $B$ has this form.) Define the 'active index set' $I_{x_0} = \{ i \in I | g_i(x_0) = 0 \}$. 
Lemma: $x_0$ is an extreme point of $C$ iff $x_0 \in C$ and $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$.
Proof: ($\implies$): Suppose $x_0$ is an extreme point of $C$, but $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} \neq  \mathbb{R}^n$. Then choose a non-zero $h \in \mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}}^{\bot}$. Furthermore note that if $ i \notin I_{x_0}$, then there exists a neighborhood $U$ of $x_0$ such that $i \notin I_x$, forall $x \in U$. Now consider the points $x_0 + \lambda h$, and observe that for $\lambda$ small enough, $x_0 \pm\lambda h \in C$ (since all constraints are satisfied). We can write $x_0 = \frac{1}{2} ( (x_0+\lambda h) + (x_0-\lambda h))$ which contradicts the fact that $x_0$ is extreme.
($\impliedby$): Now suppose $x_0 \in C$ and $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}} = \mathbb{R}^n$. Suppose $x_0 = \lambda x + (1-\lambda) y$, with $x,y \in C$, and $\lambda \in (0,1)$. Let $i \in I_{x_0}$, then $g_i(x_0) = \lambda g_i(x) + (1-\lambda) g_i(y) = 0$. It follows that $g_i(x) = g_i(y) = 0$, from which we have $\langle \gamma_i, x_0 \rangle = \langle \gamma_i, x \rangle = \langle \gamma_i, y \rangle$, for all $i \in I_{x_0}$. However, this implies that $x_0-x$ and $x_0-y$ lie in the complement of $\mathbb{sp} \{ \gamma_i \}_{i \in I_{x_0}}$, which is $\{ 0 \}$ by assumption. Hence $x = y = x_0$. It follows that $x_0$ is extreme.
Now back to the set $B$. Let $x$ be an extreme point of $B$. $B$ is defined by $2n+1$ constraints, however of the $2n$ constraints $x_i \in [0,1]$, at most $n$ can be active. Hence at most $n+1$ constraints can be active (and any $n$ of these are linearly independent).
There are two possibilities: (1) $x_1+...+x_n = k$. In this case, $n-1$ of the other constraints must be active (ie, $x_i$ is either $0$ or $1$ for $n-1$ indices $i$). Since $k$ is an integer, it then follows that the remaining $x_i$ must also be $0$ or $1$. Thus $x = \sum_{j \in J} e_j$, where $|J| = k$. (2) $x_1+...+x_n < k$. In this case all of the $x_i$ must be either $0$ or $1$ (at most $k-1$ can be $1$, of course). This gives $x = \sum_{j \in J} e_j$, where $|J| < k$.
This characterizes the extreme points of $B$ as having the form $x = \sum_{j \in J} e_j$, where $|J| \leq k$, and it a straightforward observation to note that all such $x$ satisfy $x \in A$. Hence we have the desired result.
