The following function measures the statistical difference between two discrete probability distributions. This was given to me by a friend.
$\displaystyle \large f(n) = \sum_{i=1}^n |x_i - y_i| $
It is known that $\displaystyle \large \sum_{i=1}^n x_i = \sum_{i=1}^n y_i = 1 \, \bigwedge \, 0 \leqslant x_i, y_i \leqslant 1$
Conjecture:
$\displaystyle \large f(n) \leqslant 2 \, \forall \, n \in \mathbb{Z}^+ \, \text{\ } \{1\}$
My attempt:
The function is the taxicab distance between two points that lie on the region defined by:
$\displaystyle \large 0 \leqslant a_i \leqslant 1 \bigwedge \sum_{i=1}^n a_i = 1$
By the extended triangle inequality, the taxicab distance must be strictly greater than the euclidean distance between the two points.
Therefore, the larger the euclidean distance, the larger the taxicab distance.
The largest possible euclidean distance occurs when the two points are as far as possible from each other, which occurs when the two points occupy a different corner on the $(n-1)$-dimensional region defined by the restrictions, in the corresponding $n$-dimensional space.
With this maximisation of the euclidean distance, the taxicab distance is immediately fixed and is also maximised.
By simple computation, that maximum distance is $2$ units.
$\large \mathcal{Q.E.D.}$
Is my proof correct? If not, a correct proof would be nice. My friend also insists that the proof be algebraic, not geometric, for personal ease of comprehension.
I think your proof is correct, although the "simple calculation" at the end is a crucial part of it and should be written out.
The simplest way to prove this is to use the triangle inequality pointwise: $$\sum_{i=1}^n|x_i-y_i|\leq \sum_{i=1}^n(|x_i|+|y_i|)=\sum_{i=1}^n|x_i|+\sum_{i=1}^n|y_i|=1+1.$$