What is the maximal value of $ 2x_1+2^2 x_2+2^3 x_3+\cdots+2^{n}x_n ?$

Question

Find a maximum value (or any good estimating) of the expression $$ 2x_1+2^2 x_2+2^3 x_3+\cdots+2^{n}x_n $$ subject to the following restrictions: \begin{cases} x_1+x_2+\cdots+x_n=n+1,\\ x_1+2x_2+\cdots+n x_n=m \end{cases} Here $x_i,n,m$ all are natural numbers ($x_i$ can be zero), $n,m>0.$ So, I am looking for a constant $K(n,m)$ such that $$ 2x_1+2^2 x_2+2^3 x_3+\cdots+2^{n}x_n\leq (<) K(n,m). $$ By CS I get $$ 2x_1+2^2 x_2+2^3 x_3+\cdots+2^{n}x_n \leq \sqrt{2^2+2^4+2^6+\cdots 2^{2n}} \sqrt{x_1^2+x_2^2+\cdots+x_n^2}< \sqrt{\frac{4^{n+1}-4}{3}} \sqrt{(x_1+x_2+\cdots+x_n)^2}=(n+1)\sqrt{\frac{(4^{n+1}-4)}{3}}. $$ But seems it is very bad estimate even without $m.$ Any ideas?

Answer 1

As it turns out, it will be useful to represent $m$ using two additional quantities ($q$ and $r$) defined by equality $m=(n+1)+(n-1)q+r$, where $q$ and $r$ are the non-negative integer quotient and remainder obtained by dividing $(m-(n+1))$ by $(n-1)$.

Now, let the $n$-tuple $(x_1, x_2, \ldots, x_n)$ be optimal; i.e. satisfying both equations, while attaining the maximal value of $\sum_{i=1}^n 2^ix_i$.

If there was index $2\leq s\leq (n-1)$ with $x_i\geq 2$, we could replace three terms in the tuple as follows: $$\begin{array}{lclcl} x_{s-1} & \rightarrow & x_{s-1} & + & 1 \\ x_{s} & \rightarrow & x_{s} & - & 2 \\ x_{s+1} & \rightarrow & x_{s} & + & 1 \\ \end{array}$$

The resulting tuple would also satisfy both equations, but the sum would have increased by $2^{s-1}$; contradicting the optimality of our chosen tuple.

Quick note: If we relaxed the conditions on $x_i$ being non-negative integers to being non-negative reals, we would be done: Instead of $(+1)$ and $(-2)$, we could have used $(+\frac{1}{2}x_s)$ and $(-x_s)$, thus replacing $x_s$ by zero. This would allow us to conclude that optimality can only be achieved if $x_i=0$ for all $2\leq i\leq (n-1)$. The two equations given by the problem statement would simplify as $$\begin{array}{lcl} x_1 + x_n & = & (n+1)\\ x_1 + nx_n & = & m \end{array}$$

with the unique (and therefore optimal) solution of $x_n = \frac{m-(n+1)}{n-1} = q+\frac{r}{n-1}$ and $x_1=(n+1)-x_n$. The value of the sum would them be $$Best_{\text{relax}} = 2^nq + 2(n+1-q) + \frac{r}{n-1}(2^n-2)$$ This is the attainable maximum for the relaxed problem, and thus also an upper bound for the integers-restricted one.

Since we are dealing with integers, we need to do a bit more work: we have only established that $x_i\in\{0,1\}$ for $2\leq i\leq (n-1)$. However, if there were any two indices $2\leq s<t\leq (n-1)$ with $x_s=x_t=1$, we could improve the value of the sum by replacing $$\begin{array}{lclcl} x_{s-1} & \rightarrow & x_{s-1} & + & 1 \\ x_{s} & \rightarrow & x_{s} & - & 1 \\ x_{t} & \rightarrow & x_{t} & - & 1 \\ x_{t+1} & \rightarrow & x_{t+1} & + & 1 \\ \end{array}$$

This would increase the sum $\sum_{i=1}^n 2^ix_i$ by $(2^t - 2^{s-1})$, contradicting the optimality of our choice again.

Thus, the optimum can only be reached if all $x_i$ with $2\leq i\leq (n-1)$ are equal to zero, with the possible exception of a single one which must then be equal to $1$.

There are two cases to consider, depending on $r$ being equal to zero or greater than zero. The first case is simple and we have already dealt with it in the note above: It results in $x_n=q$ and $x_1=(n+1)-q$. This yields the value of the sum as $$Best_{\text{zero}} = 2^nq + 2(n+1-q)$$

For the other case, let $x_s=1$ be the sole non-zero value with $2\leq s\leq (n-1)$. The two given equations can be simplified as

$$\begin{array}{lcl} x_1 + 1 + x_n & = & (n+1)\\ x_1 + s + nx_n & = & m \end{array}$$

Subtracting the two yields $(s-1) + (n-1)x_n = (n-1)q+r$. Since $1\leq (s-1)\leq (n-2)$, we can only have equality if $(s-1)=r$, $x_n = q$ and, consequently, $x_1=(n-q)$. The sum is then equal to $$Best_{\text{nonzero}} = 2^nq + 2(n+2^r(r+1)-q)$$

As it turns out, this expression agrees with the one for $r=0$, so we can simply state that the optimum in case of non-negative integers is: $$Best = 2^nq + 2(n+2^r(r+1)-q)$$