MathB.in - Share Mathematics with LaTeX and Markdown

Claim: Let $k \in \mathbb{N}$ and let $(\lambda_{j})_{j \in \{1,\ldots,k\}}$ be a vector of parameters such that $\lambda_{j} \geq 0$. Prove that 
$\sum_{j=1}^{k} \lambda_{j} = 1$ $\Rightarrow$ $\forall j \in \{1,\ldots,k\}$, $\lambda_{j} \leq 1$.

Proof: Suppose not, i.e., $\exists i \in \{1,\ldots,k\}$ such that $\lambda_{j} > 1$. Then, $$\sum_{j=1}^{k} \lambda_{j} = \lambda_{i} + \sum_{j=1; j \neq i}^{k} \lambda_{j} > 1 + \sum_{j=1; j \neq i}^{k} \lambda_{j} \geq 1+(0+\cdots+0) = 1,$$ as $\forall i \in \{1,\ldots,j-1,j+1,\ldots,k\}$, $\lambda_{i} \geq 0$. Therefore, we establish that $\sum_{i=1}^{k} \lambda_{i} > 1$, a contradiction.

What did we do here? 
--------------------

Let $A$ be the statement "$\sum_{j=1}^{k} \lambda_{j} = 1$'' and $B$ be the statement "$\forall j \in \{1,\ldots,k\}$ such that $\lambda_{j} \leq 1$''.  Claim asks you to prove $A \Rightarrow B$. This is equivalent to proving its contrapositive, i.e., $\lnot B \Rightarrow \lnot A$. Therefore, it is equivalent to proving that $\exists j \in \{1,\ldots,k\}$ such that $\lambda_{j} > 1$ $\Rightarrow$ $\sum_{j=1}^{k} \lambda_{j} \neq 1$.

Let's try proving it directly, $A \Rightarrow B$. We will use induction method here to proof that $\sum_{j=1}^{k} \lambda_{j} = 1$ $\Rightarrow$ $\forall j \in \{1,\ldots,k\}$, $\lambda_{j} \leq 1$.

Base case
---------
For $k=1$ we have $\sum_{j=1}^1 \lambda_{j} = \lambda_{1} = 1$ satisfying $\lambda_{1} \leq 1$.

Inductive Step
--------------
Assuming that the claim holds for $k=n$ i.e. if $\sum_{j=1}^n \lambda_{j} = 1$ then $\lambda_{j} \leq 1 \forall j \in \{1,\ldots,n\}$, we must prove it holds for $k=n+1$, i.e., if $\sum_{j=1}^{n+1} \lambda_{j} = 1$, then $\lambda_{j} \leq 1 \forall j \in \{1,\ldots,n\}$

Consider that $\sum_{j=1}^{n+1} \lambda_{j} = \lambda_{n+1} + \sum_{j=1}^{n} \lambda_{j} = \lambda_{n+1} + 1$.

Since $\sum_{j=1}^{n+1} \lambda_{j} = 1$, we have $\lambda_{n+1} + 1 = 1 \Rightarrow \lambda_{n+1} = 0$.

Now $\lambda_{n+1} = 0 \leq 1$ by definition.

Thus, by the  induction hypothesis, we know that $\lambda_{j} \leq 1\forall j \in \{1,\ldots,n\}$. Since, $\lambda_{n+1} = 0 \leq 1$ it follows that $\lambda_{j} \leq 1\forall j \in \{1,\ldots,n\}$.

Thus, by induction, the claim holds for all positive integers $k$.

Without Induction
-----------------
Given that $\sum_{j=1}^k \lambda_j = 1$ and $\lambda_j \geq 0 \forall j$ we want to show that $\lambda_{j} \leq 1 \forall j \in \{1,\ldots,n\}$.

Let's denote the $\sum_{j=1}^k \lambda_j = S$

$\Rightarrow S = \sum_{j=1}^k \lambda_j = 1$

Let $\lambda_{l} \in \{\lambda_j | j \in \{1,\ldots,n\}$ representing any $l^{th} \text{term} \in \{1,\ldots, l , \dots, n\}$.

So we have, $\sum_{j=1}^k \lambda_j = \sum_{j=1}^{k-l} \lambda_j+ \lambda_l = 1$

$\Rightarrow \lambda_l = 1 - \sum_{j=1}^{k-l} \lambda_j \leq 1$.

This shows that $\lambda_l \leq 1$ for any $l$ in the given range. Thus, each $\lambda_l$ is less than or equal to 1.

The Main Proof Problem:
---------
THEOREM 2.1.1.

The set $X \subset \mathbb{R}^n$ is convex if and only if $k\in\mathbb{N}, x^1, x^2, \ldots, x^k \in X, \lambda_k \geq 0 \forall k$.

$\sum_{i=1}^k \lambda_i = 1 \Rightarrow \sum_{i=1}^k \lambda_i x^i \in X$

Proof:
------
Here in the theorem set $X \subset \mathbb{R}^n$ is convex $\iff$ for any $k\in\mathbb{N}, x^1, x^2, \ldots, x^k \in X, \lambda_k \geq 0 \forall k$, if $\sum_{i=1}^k\lambda_i = 1\Rightarrow \sum_{i=1}^k \lambda_i x^i \in X$.
So, we must prove two sets of implications:

IMPLICATION 1:
-------------
 Convexity of $X \subset \mathbb{R}^n$ implies for any $k\in\mathbb{N}, x^1, x^2, \ldots, x^k \in X, \lambda_k \geq 0 \forall k$, if $\sum_{i=1}^k\lambda_i = 1\Rightarrow \sum_{i=1}^k \lambda_i x^i \in X$.

Let $x \subset \mathbb{R}^n$ be a convex set. Suppose $k \in \mathbb{N}, x^1, ^2,\ldots,x^k \in X$ and $\lambda_1, \lambda_2, \ldots , \lambda_k \geq 0$ with $\sum_{i=1}^k \lambda_i = 1$. We intend to show that $\sum_{i=1}^k \lambda_i x^i \in X$. By convexity of X, for any $x^i,x^j  \in X$, and $\lambda \in [0,1]$ we have $\lambda x^i + (1-\lambda)x^j \in X$. Now, let's try proving using induction.

Base step (k =  2):
--------------
Let $y_1$ be an element of the weighted sum set, given by the convex combination of $x^i$ and $\lambda_i$. So, $y_1 = \lambda_1 x^1 + (1- \lambda_1) x^2$. Now, as $x^1, x^2, \ldots, x^k \in X$ is convex, $y_1 \in X$ by definition.

IMPLICATION 2: 
--------------
For any $k\in\mathbb{N}, x^1, x^2, \ldots, x^k \in X, \lambda_k \geq 0 \forall k$, if $\sum_{i=1}^k\lambda_i = 1\Rightarrow \sum_{i=1}^k \lambda_i x^i \in X$ implies $X \subset \mathbb{R}^n$ is convex.

Tue, 20 Feb 2024 17:23 GMT