Help with proof with greatest integer function

**rubik mania** · Nov 15th 2009, 08:46 AM

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!

**hatsoff** · Nov 15th 2009, 07:03 PM

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$

**rubik mania** · Nov 15th 2009, 07:25 PM

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.

**rubik mania** · Nov 17th 2009, 05:04 PM

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?

Thread: Help with proof with greatest integer function

LinkBack

Thread Tools

Display

Help with proof with greatest integer function

Similar Math Help Forum Discussions

Greatest Integer Function

Greatest integer function limit?

Limits of the Greatest Integer Function

Greatest integer function

Greatest Integer Function

Search Tags