Thread: Help with proof with greatest integer function

I'm having a hard time with this proof:
Show that if a and b are positive integers then
$\displaystyle \sum_{i = 1}^{[a/2]} [\frac{ib}{a}] + \sum_{j = 1}^{[b/2]} [\frac{ja}{b}] = [\frac{a}{2}][\frac{b}{2}] + [\frac{(a,b)}{2}]$

Thanks everyone!

Originally Posted by rubik mania

I'm having a hard time with this proof:
Show that if a and b are positive integers then
$\displaystyle \sum_{i = 1}^{[a/2]} [\frac{ib}{a}] + \sum_{j = 1}^{[b/2]} [\frac{ja}{b}] = [\frac{a}{2}][\frac{b}{2}] + [\frac{(a,b)}{2}]$

Thanks everyone!

You must have written this down wrong, because we can disprove it by letting $\displaystyle a=4$ and $\displaystyle b=8$. Then

$\displaystyle \sum_{i = 1}^{a/2}\frac{ib}{a} + \sum_{j = 1}^{b/2}\frac{ja}{b}=\sum_{i = 1}^{4/2}\frac{i8}{4} + \sum_{j = 1}^{8/2}\frac{j4}{8}$

$\displaystyle =2\sum_{i = 1}^{2}i + \frac{1}{2}\sum_{j = 1}^{4}j$

$\displaystyle =2(1+2) + \frac{1}{2}(1+2+3+4)$

$\displaystyle =6+ 5$

$\displaystyle =11$.

But $\displaystyle \frac{a}{2}\left(\frac{b}{2}\right)+\frac{(a,b)}{2 }=\frac{4}{2}\left(\frac{8}{2}\right)+\frac{(4,8)} {2}$

$\displaystyle =2\left(4\right)+\frac{4}{2}$

$\displaystyle =8+2$

$\displaystyle =10\neq11$.

So your proof is impossible without further parameters.

Here is a proper rendering:

$\displaystyle \sum_{i = 1}^{a/2}\frac{ib}{a} + \sum_{j = 1}^{b/2}\frac{ja}{b} =\frac{b}{a}\sum_{i = 1}^{a/2}i+\frac{a}{b}\sum_{j = 1}^{b/2}j$

$\displaystyle =\frac{b}{a}\left(\frac{(a/2)(a/2+1)}{2}\right)+\frac{a}{b}\left(\frac{(b/2)(b/2+1)}{2}\right)$

$\displaystyle =\frac{b}{a}\left(\frac{a^2/4+a/2}{2}\right)+\frac{a}{b}\left(\frac{b^2/4+b/2}{2}\right)$

$\displaystyle =b\left(\frac{a+2}{8}\right)+a\left(\frac{b+2}{8}\ right)$

$\displaystyle =\frac{ab+2b+ab+2a}{8}$

$\displaystyle =\frac{ab+a+b}{4}$. $\displaystyle \blacksquare$

Sorry, I forgot to mention:[x] is the greatest integer function.

so $\displaystyle \sum_{i = 1}^{a/2}[\frac{ib}{a}] + \sum_{j = 1}^{b/2}[\frac{ja}{b}]=\sum_{i = 1}^{4/2}[\frac{i8}{4}] + \sum_{j = 1}^{8/2}[\frac{j4}{8}]$
$\displaystyle = (2 + 4) + ([4/8] + [8/8] + [12/8] + [16/8])$
$\displaystyle = 6 + 0 + 1 + 1 + 2 = 10$, so it actually works.

ok, this is what I have so far...
Let $\displaystyle \ell$ be the set of all pairs of integers (x,y) satisfying
$\displaystyle 1 \leq x \leq \left[\frac{a}{2}\right], 1 \leq y \leq \left[\frac{b}{2}\right]$

The set $\displaystyle \ell$ has $\displaystyle \left[\frac{a}{2}\right]\left[\frac{b}{2}\right]$ members

Separate $\displaystyle \ell$ into subsets $\displaystyle \ell_1 \& \ell_2$, according as $\displaystyle bx < ay, \mbox{ or } bx > ay$

The set $\displaystyle \ell_1$ can be described as the set of all pairs (x,y) such that $\displaystyle 1 \leq x \leq \left[\frac{a}{b}\right], 1 \leq y \leq \frac{bx}{a}$

The number of pairs in $\displaystyle \ell_1$ is then seen to be $\displaystyle \sum_{x = 1}^{[a/2]} \left[\frac{bx}{a}\right]$


Similarly, $\displaystyle \ell_2$ consists of the pairs of (x,y) such that
$\displaystyle 1 \leq y \leq \left[\frac{b}{2}\right], 1 \leq x \leq \frac{ay}{b}$
and the number of pairs in $\displaystyle \ell_2$ is $\displaystyle \sum_{y = 1}^{[b/2]} \left[\frac{ay}{b}\right]$

Now this is where I am still stuck on:
somehow, when you account for $\displaystyle bx = ay$, there may be a third set, that is somehow equivalent to $\displaystyle \left[\frac{(a,b)}{2}\right]$ number of elements total. How do you show that this is true?