3

Is there a tight upper bound on $\sum_{i=1}^n \sum_{j=1}^m \min(a \cdot i,b \cdot j)$ for any $a,b \in \mathbb{R}^+$

For example one upper bound would be \begin{align} \sum_{i=1}^n \sum_{j=1}^m \min(a \cdot i,b \cdot j) \le \min \left(a \cdot \sum_{i=1}^n \sum_{j=1}^m i,b \cdot \sum_{i=1}^n \sum_{j=1}^m j \right) \end{align}

Is there a better approach?? Thank you

Edit:

Note that w.l.o.g. we can set $a=1$.

Boby
  • 5,985
  • 1
    Split the problem into cases and calculate the double sum. You can look at the intervals $[a,na]$ and $[b,mb]$ and assume without loss of generality that $a<b$ (because of symmetry). Then the intervals can be disjoint or overlap in several ways, in each case giving you an explicit value for the minimum. For the actual calculations, all you need is the fact that the sum of the first $n$ positive integers is equal to $n(n+1)/2$. – herrsimon Sep 18 '14 at 20:19
  • @herrsimon could you explain a bit more. Why intervals $[a,na]$ and $[b,mb]$? – Boby Sep 18 '14 at 20:23
  • These are the extremal values of $ai$ and $bj$. – herrsimon Sep 18 '14 at 20:24
  • 1
    I do one simple case for you: Still assuming $a<b$, if $[a,na]$ and $[b,mb]$ do not overlap, i.e. $na \leq b$, then $ai \leq an \leq b \leq bj$ which implies that $\operatorname{min}(ai,bj)=ai$. Therefore, $\sum_{i=1}^n \sum_{j=1}^m \operatorname{min}(ai,bj) = \sum_{i=1}^n \sum_{j=1}^m ai = a \sum_{i=1}^n i \sum_{j=1}^m = a m n (n+1)/2$. The overlapping cases are a bit trickier but work analogously. – herrsimon Sep 18 '14 at 20:27
  • Thanks. I will try. Do yo mind if I bug you a little more with question if I don't succeed? – Boby Sep 18 '14 at 20:30
  • Try and if you have more questions, ask them. If I'm not here to answer them, I'm sure that somebody else will. By the way, just to give you a better understanding: For finite sums, there is always a tight upper and lower bound, namely the value of the sum, which you (or a computer) can explicitly calculate. – herrsimon Sep 18 '14 at 20:43
  • Yes. I need an analytical one though – Boby Sep 18 '14 at 20:45
  • @herrsimon I've been try to analyze all the cases but keep running into issues. Could help me with identifying all the cases. – Boby Sep 18 '14 at 22:16

1 Answers1

1

This upper bound is surely not the tightest, but it's a cool approach i believe:

$$ \begin{align} \sum_{i=1}^n \sum_{j=1}^m \min(a \cdot i,b \cdot j) \le & \sum_{i=1}^n \sum_{j=1}^m \frac{a \cdot i+b \cdot j}{2}=\\ &=\sum_{j=1}^m \sum_{i=1}^n \frac{a \cdot i}{2}+\sum_{i=1}^n \sum_{j=1}^m \frac{b \cdot j}{2}=\\ &=\frac{am}{2}\sum_{i=1}^n i+\frac{bn}{2}\sum_{j=1}^m j=\\ &=\frac{am}{2}\cdot\frac{n(n+1)}{2}+\frac{bn}{2}\cdot\frac{m(m+1)}{2}=\\ &=\frac{mn}{4}\Big[a(n+1)+b(m+1)\Big] \end{align} $$ so more concisely: $$ \sum_{i=1}^n \sum_{j=1}^m \min(a \cdot i,b \cdot j) \le \frac{mn}{4}\Big[a(n+1)+b(m+1)\Big] $$

by the way your upper bound can be written more concisely: $$ \sum_{i=1}^n \sum_{j=1}^m \min(a \cdot i,b \cdot j) \le \frac{mn}{2}\min\Big(a(n+1),b(m+1)\Big) $$ so you found a better upper bound apparently :D

mini-proof for: $\ \ \ \ \ \min(a,b)\le\frac{a+b}{2}$
given $a,b \in \mathbb{R}| a \le b$: $$ min(a,b)=a\\ a\le b \iff a+a\le b+a \iff \frac{a+a}{2}\le \frac{a+b}{2} \iff a\le \frac{a+b}{2} \implies\\ \implies\min(a,b)=a\le \frac{a+b}{2} $$ if $a>b$ just swap the letters in the proof :)

writing min(a,b) as an analytic function: $$\min(a,b)= \frac{a+b-|a-b|}{2} = \frac{a+b-\sqrt{(a-b)^2}}{2} $$

Frank
  • 2,348
  • Question. Is $min(a,b) \le \frac{a+b}{2}$?? – Boby Sep 18 '14 at 21:15
  • always, i edited my answer and i added a mini proof for that inequality. – Frank Sep 18 '14 at 21:29
  • Hey. Is there a way to write min(a,b) is an analytic function? Maybe that can work? – Boby Sep 18 '14 at 21:30
  • there is a cumbersome way to do it, re-edited the answer. – Frank Sep 18 '14 at 21:41
  • Yes. But this will not solve it. Because $|a-b|$ doesn't sum well. – Boby Sep 18 '14 at 21:42
  • you could do $|a-b| = \sqrt{(a-b)^2}$ but i doubt that helps.. – Frank Sep 18 '14 at 21:46
  • Yes. I just tried. It does not. – Boby Sep 18 '14 at 21:57
  • search this on wolfram alpha: $\ \ \ \ \mbox{sum_(i=1)^n sum_(j=1)^m min(i,j)}\ \ \ \ $ i'm, starting to believe that what you are looking for does not exist... – Frank Sep 18 '14 at 22:05
  • since this question has kept me busy, i decided to upvote it! – Frank Sep 18 '14 at 22:06
  • By doesn't exist you mean no one ever tried it? – Boby Sep 18 '14 at 22:06
  • 1
    no, what i meant was more like: it cannot be done the way you want it... the only reasonable way would be to examine cases, like someone suggested in the comments to your question. – Frank Sep 18 '14 at 22:09
  • I see. But I think some cases a very difficult and probably can not be done as well. – Boby Sep 18 '14 at 22:11
  • @Franceso Alem Do you think I should put it as a bounty question? Is this interesting to the community at all or not? – Boby Sep 18 '14 at 22:34
  • i do not think you'll get an answer that deserves the bounty, but try if this problem is really important to you :) – Frank Sep 18 '14 at 22:50
  • Thanks. You see all I am looking for is the bound that is slightly better than the one I have. Even by a constant. – Boby Sep 18 '14 at 22:53