# Help with proof with greatest integer function

• Nov 15th 2009, 09:46 AM
rubik mania
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
$\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!
• Nov 15th 2009, 08:03 PM
hatsoff
Quote:

Originally Posted by rubik mania
I'm having a hard time with this proof:
Show that if a and b are positive integers then
$\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 $a=4$ and $b=8$. Then

$\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}$

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

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

$=6+ 5$

$=11$.

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

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

$=8+2$

$=10\neq11$.

So your proof is impossible without further parameters.

Here is a proper rendering:

$\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$

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

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

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

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

$=\frac{ab+a+b}{4}$. $\blacksquare$
• Nov 15th 2009, 08:25 PM
rubik mania
Sorry, I forgot to mention:[x] is the greatest integer function.

so $\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}]$
$= (2 + 4) + ([4/8] + [8/8] + [12/8] + [16/8])$
$= 6 + 0 + 1 + 1 + 2 = 10$, so it actually works.
• Nov 17th 2009, 06:04 PM
rubik mania
ok, this is what I have so far...
Let $\ell$ be the set of all pairs of integers (x,y) satisfying
$1 \leq x \leq \left[\frac{a}{2}\right], 1 \leq y \leq \left[\frac{b}{2}\right]$

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

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

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

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

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

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