# Algebraic manipulation of floors and ceilings

I am trying to solve the summation

$$\sum_{n=3}^{\infty} \frac{1}{2^n} \sum_{i=3}^{n} \left\lceil\frac{i-2}{2}\right\rceil$$

I will list some of the simplifications that I've found so far, and then get around to asking my question. Please feel free to point out any logical errors that I have (in all likelihood) made.

$$\sum_{n=3}^{\infty} \frac{1}{2^n} \sum_{i=1}^{n-2} \left\lceil\frac{i}{2}\right\rceil$$

$$\sum_{n=3}^{\infty} \frac{1}{2^n} \left(\sum_{i=1}^{\left\lceil\frac{n-2}{2}\right\rceil} i+ \sum_{i=1}^{\left\lfloor\frac{n-2}{2}\right\rfloor} i\right)$$

Since the upper bound in both of the inner summations will be an integer, I have:

$$\sum_{n=3}^{\infty} \frac{1}{2^n} \left(\frac{\left\lceil\frac{n-2}{2}\right\rceil\left(\left\lceil\frac{n-2}{2}\right\rceil + 1\right)}{2}+\frac{\left\lfloor\frac{n-2}{2}\right\rfloor\left(\left\lfloor\frac{n-2}{2}\right\rfloor + 1\right)}{2}\right)$$

How do I simplify a floor times a floor and a ceiling times a ceiling algebraically?

I'm thinking that the identity

$$n = \left\lceil\frac{n}{2}\right\rceil + \left\lfloor\frac{n}{2}\right\rfloor$$

might come in handy, but I have very little experience manipulating floors and ceilings algebraically. Let me be clear: I'm not looking for an answer to the summation, just guidance in simplifying this current step.

-
Did you look at the Wikipedia article Floor and Ceiling Functions. I found some interesting properties there for some other problem. – mvw Jun 25 '14 at 14:48
Do you really mean what you wrote, or should that be $\lceil \dfrac{i-2}{2}\rceil$ instead of $\lceil \dfrac{n-2}{2}\rceil$? – Robert Israel Jun 25 '14 at 14:50
Should that be $$\sum_{n=3}^{\infty} \frac{1}{2^n} \sum_{i=3}^{n} \left\lceil\frac{i-2}{2}\right\rceil?$$ Otherwise the $i$ isn't really doing anything, and you can quickly simplify that inner sum. – Dustan Levenstein Jun 25 '14 at 14:51
If so, get rid of the $\lceil \rceil$ by splitting into the two cases $i$ even and $i$ odd. – Robert Israel Jun 25 '14 at 14:52
Thanks, fixed the mistake, I did mean $\left\lceil\frac{i-2}{2}\right\rceil$. – Jon Poler Jun 25 '14 at 15:11

Start with the generating function for $\displaystyle a_i=\left\lceil \frac{i-2}{2}\right\rceil\; , i\ge 3$

which turns out to be

\begin{align*} G(x) &= \frac{x^3}{1-x-x^2+x^3} \end{align*}

and for the sum of the coefficients, it's

\begin{align*} H(x) &= \frac{1}{1-x}\, G(x) \end{align*}

and the required answer is $\displaystyle H\left(\frac{1}{2}\right)$

-

\begin{align*}S&=\sum_{n=3}^\infty\frac{1}{2^n}\sum_{i=3}^n\left\lceil\frac{i-2}{2}\right\rceil&=\sum_{n=3}^\infty\frac{1}{2^n}\sum_{i=3}^n\left\lfloor\frac{i-1}{2}\right\rfloor\\ &=\sum_{n=3}^\infty\frac{1}{2^n}\sum_{i=2}^{n-1}\left\lfloor\frac{i}{2}\right\rfloor &=\sum_{n=3}^\infty\frac{1}{2^n}\left\lfloor\frac{(n-1)^2}{4}\right\rfloor\end{align*} with $n=2m\quad$ then $\displaystyle\quad S_{2m}=\sum_{m=2}^\infty\frac{1}{2^{2m}}\left\lfloor\frac{(2m-1)^2}{4}\right\rfloor=\sum_{m=2}^\infty\frac{m^2-m}{2^{2m}}=\sum_{m=1}^\infty\frac{m^2+m}{2^{2m+2}}$

with $n=2m+1\quad$ then $\displaystyle\quad S_{2m+1}=\sum_{m=1}^\infty\frac{1}{2^{2m+1}}\left\lfloor\frac{(2m)^2}{4}\right\rfloor=\sum_{m=1}^\infty\frac{m^2}{2^{2m+1}}$

So $\displaystyle\quad S=S_{2m}+S_{2m+1}=\sum_{m=1}^\infty\frac{3m^2+m}{4^{m+1}}=\boxed{\frac{2}{3}}$

-