0
$\begingroup$

For some positive integer constants $n, k$ and $t$, I want to find the values for $n_1, \ldots, n_t$, all positive integers, that maximize the following sum :

$$ \sum_{i = 1}^t (n_i)^k $$

such that $n_i \geq 1$ for each $i$ and $\sum_{i = 1}^t n_i = n$. So, what's the best way to pick the $n_i$'s ?

It feels like the right choice is to let $n_1 = n - t + 1$ and $n_2 = n_3 = \ldots = n_t = 1$. But my attempts to prove this go through a lot of tedious steps, though this seems simple enough. So, does anyone have a proof for this ?

EDIT :

In the event someone has the same question, here's the proof, following answerer's advice.

Let's try induction on $t$ (assuming $t < n$). I want to show that $\sum_{i = 1}^t (n_i)^k \leq (n - t + 1)^k + t - 1$. True for $t = 1$, base case covered. Now,

$$ \sum_{i = 1}^t (n_i)^k = \sum_{i = 1}^{t - 1} (n_i)^k + n_t^k \leq (n - n_t - t + 2)^k + t - 2 + n_t^k $$

by induction. Letting $n_0 = n - n_t -t +2$, we get another sum of the same type with $t = 2$:

$$ n_0^k + n_t^k + t - 2 \leq (n_0 + n_t - 2 + 1)^k + (2 - 1) + t - 2 \\ = (n - n_t - t + 2 + n_t - 2 + 1)^k + t - 1\\ = (n - t + 1)^k + t - 1 $$

$\endgroup$
0
$\begingroup$

I think your intuition is correct for the solution (for $k>1$), and I would prove it by considering $t=2$ and then using an inductive argument for any $t$ up to $n-1$.

$\endgroup$
  • $\begingroup$ Yeah, that works fine, thanks. I included the answer in my question. $\endgroup$ – Manuel Lafond Jan 22 '15 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.