1

If $a_i = 1 - \frac{1}{N_i}$ and $\sum\limits_{I=0}^k{N_i} = n$, then what is the maximum and minimum values of $\sum\limits_{I=0}^k{a_i}$? Please help, I've tried to solve it but then I got confused. I think I may of found the minimum value to be $\frac{n - k}{n - k + 1}$ but i'm not sure.

Also $N_i > 0$ and $N_i$ is a subset of $\mathbb{N}$

Harry Obey
  • 21
  • 1
  • 3
  • maybe is useful to add $N_i > 0$ and are natural numbers? For clarity. – Chip Apr 19 '16 at 03:29
  • you can use Lagrange multipliers to find the extrema. For a simpler solution to find one extremum, you can use the inequality between the harmonic average and the arithmetic average of the $a_i$ terms. – Chip Apr 19 '16 at 04:43
  • In Response to Chip: Yeah, sorry for missing that, I just added it in. Thanks for telling me. – Harry Obey Apr 19 '16 at 05:32
  • Also to Chip: I am from high school and I don't have a strong basis of Higher level mathematics i.e. don't know anything about Lagrange multipliers and harmonic average. – Harry Obey Apr 19 '16 at 05:35
  • i understand...then you can use the inequality of harmonic and arithmetic means: https://en.wikipedia.org/wiki/Harmonic_mean and https://en.wikipedia.org/wiki/Arithmetic_mean and this should find you one of the extremum values you look for. – Chip Apr 19 '16 at 06:50
  • I can't use the inequality as the condition is that all $N_1 = N_2 = ... = N_k$ But this is not the case, thus I can't use this inequality. – Harry Obey Apr 19 '16 at 11:11
  • I have looked at the wiki but it still doesn't help me, I can't find a HM AM Inequality. – Harry Obey Apr 20 '16 at 04:25
  • have a look here https://www.google.com.sg/url?sa=t&rct=j&q=&esrc=s&source=web&cd=13&cad=rja&uact=8&ved=0ahUKEwiQwbiIuZzMAhWCVY4KHUrACUoQFghZMAw&url=http%3A%2F%2Fwww.math.washington.edu%2F~dumitriu%2FInequalities&usg=AFQjCNGxOEY_9J6ptRAOZ5kBYMfHqpkbnQ&sig2=2LVQ4npsxrcn52wlAMMlTg . It says that $$\frac{n}{\sum ; \frac{1}{a_i}} \le \frac{\sum a_i}{n}$$. – Chip Apr 20 '16 at 05:10
  • Thanks, I found the max. But how do I find the minimum. – Harry Obey Apr 21 '16 at 10:03

1 Answers1

1

Firstly, note that

$$\sum_{i=0}^k a_i = \sum_{i=0}^k \left(1 - \frac{1}{N_i}\right) = k+1 - \sum_{i=0}^k \frac{1}{N_i} $$

If $N_i$ are arbitrary positive real numbers, then the right hand side can get arbitrarily small. However, we have $N_i \in \mathbb{N}$ for each $i$ so that $$ \sum_{i=0}^k \frac{1}{N_i} \le k+1$$ A sensible first guess to obtain the minimum for $\sum_{i=0}^k a_i$ would be to put $N_i = 1$ for $0 \le i \le k-1$ and $N_k = n-k$, thus getting $$\sum_{i=0}^k \frac{1}{N_i} = k + \frac{1}{n-k}$$ If we make any other choice, then there are at least two values $i$ such that $N_i \ge 2$ and hence $$ \sum_{i=0}^k \frac{1}{N_i} \le (k-1) + \frac{1}{2} + \frac{1}{2} = k < k + \frac{1}{n-k}$$ so our sensible first choice is the best we can do, that is

$$ \sum_{i=0}^k a_i = k+1 - \sum_{i=0}^k \frac{1}{N_i} \ge k+1 - \left(k + \frac{1}{n-k} \right) = 1 - \frac{1}{n-k}$$ and this is the minimum.

For the maximum, as mentioned in the comments you can use the AM-HM inequality to obtain

$$ \sum_{i=0}^k \frac{1}{N_i} \ge \frac{(k+1)^2}{\sum_{i=0}^k N_i}= \frac{(k+1)^2}{n} $$

so that $$\sum_{i=0}^k a_i \le k+1 - \frac{(k+1)^2}{n} $$ Equality only happens in this case if all $N_i$ are equal, which may not always be possible. I think that, in this case, you want to select the $N_i$ to be as close to being equal as possible, that is each $N_i$ should be either $\lfloor \frac{n}{k+1} \rfloor$ or $\lceil \frac{n}{k+1} \rceil$. There will essentially be just one way to do this (not counting permutations).

hexomino
  • 1,571