2

Let $a_0, a_1, \cdots, a_n \ge 0$ such that $\sum^{n}_{i=0} \frac{a_i}{2^i} = 1$.

Maximize $\sum^{n}_{i=0} a_i$ for a given fixed value $n$.

It is pretty obvious that it is maximized at $a_0 = 0, a_1 = 0, \cdots, a_{n-1} = 0, a_n = 2^n$. But is there a rigorous proof for this?

mick
  • 15,946
abc
  • 23
  • $a_i = 1 $ gives a maximum of $1+1+1+... = \infty $ ? Or do you mean for a fixed $n$ ? For a fixed $n$ it is obvious that $a_{n+1} = 0$ should be taken. It is also logical that $a_i$ should be strictly nondecreasing. – mick Feb 10 '24 at 19:32
  • 1
    @mick for fixed $n$. – abc Feb 10 '24 at 20:02

3 Answers3

4

For $0 \le i \le n$ is $$ a_i \le 2^{n-i} a_i $$ and the inequality is strict if $0 \le i \le n-1$ and $a_i \ne 0$.

Therefore is $$ \sum^{n}_{i=0} a_i \le \sum^{n}_{i=0} 2^{n-i} a_i =2^n \sum^{n}_{i=0} \frac{a_i}{2^i} = 2^n $$ with equality if and only if $a_0 = a_1 = \cdots = a_{n-1} = 0$.

Martin R
  • 113,040
3

Set $b_i=a_i/2^i$. Then the problem becomes

Maximize $\sum 2^ib_i$ such that $b_i\ge0$ for all $i$ and $\sum b_i=1.$

In this formulation it's a little more obvious that you should put unit mass on $b_n$. To be rigorous, you could say if $b_i>0$ for some $i<n$, then define $b_i':=0$ and $b_n' := b_n+b_i$, which preserves the constraints but increases the sum $\sum 2^i b_i'$.

grand_chat
  • 38,951
1

As a physical analogy we can consider the equivalent problem of $n+1$ point masses $a_i$ distribuited along a line each one at a distance $d_i = \frac1{2^i}$ from the origin such that the center of mass is located at a minimum distance

$$d=\frac{\sum_{i=0}^{n} a_i d_i}{\sum_{i=0}^{n} a_i}=\frac{1}{\sum_{i=0}^{n} a_i}$$

which can be attained at $d=d_n=\frac1{2^n}$ with $a_n=2^n$ and $a_i=0$ for all $0\le i\le n-1$.

user
  • 154,566