6
$\begingroup$

I'm trying to find a closed form for the following sum, if anyone knows a way, a hint would be much appreciated...

$$ X(n) = \sum_{i=1}^n \frac{i \choose \left \lfloor{i/2}\right \rfloor }{2^i}\ $$

The first few terms are: $$ 1 : 0.5\\ 2 : 1.0 \\ 3 : 1.375\\ 4 : 1.750\\ 5 : 2.0625\\ 6 : 2.3750\\ 7 : 2.6484375\\ 8 : 2.9218750\\ 9 : 3.16796875\\ 10 : 3.4140625\\ $$

An equivalent problem would be finding a closed form for: $$ Y(n) = \sum_{i=1}^n 2^{n-i}{i \choose \left \lfloor{i/2}\right \rfloor }\ $$ because division by $2^n$ will yield the required answer. In this case the first few terms are: $$ 1 :1\\ 2 :4\\ 3 :11\\ 4 :28\\ 5 :66\\ 6 :152\\ 7 :339\\ 8 :748\\ 9 :1622\\ $$

which in my opinion is cleaner to work with.

$\endgroup$
5
  • 2
    $\begingroup$ I'd split the sum into two sums: for even $i$ and for odd $i$ to get rid of the floor function. $\endgroup$ Apr 4, 2015 at 11:00
  • 1
    $\begingroup$ I have a problem with the numbers you give. For the $Y(n)$, I get $1,4,11,28,66,152$. Where do you think I am wrong ? $\endgroup$ Apr 4, 2015 at 11:35
  • $\begingroup$ Thank you Claude Leibovici, I spotted the mistake in my program and will correct it $\endgroup$
    – qwerty314
    Apr 4, 2015 at 12:01
  • $\begingroup$ we have the equivalence: $$\sum_{i=1}^{n}\frac{1}{2^i}\dbinom{2i}{i} \sim 2\dbinom{2n}{n}$$ $\endgroup$
    – Elaqqad
    Apr 4, 2015 at 12:54
  • $\begingroup$ See properties of the central binomial coefficient. $\endgroup$
    – Lucian
    Apr 4, 2015 at 14:07

1 Answer 1

3
$\begingroup$

Suppose we seek to evaluate $$Y(n) = \sum_{k=1}^n 2^{n-k} {k\choose\lfloor k/2\rfloor},$$

by considering $$Y_1(n) = \sum_{k=0}^{\lfloor n/2\rfloor} 2^{n-2k} {2k\choose k} \quad\text{and}\quad Y_2(n) = \sum_{k=0}^{\lfloor (n-1)/2\rfloor} 2^{n-2k-1} {2k+1\choose k}.$$

We will use the following Iverson bracket: $$[[0\le k\le n]] = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{z^k}{z^{n+1}} \frac{1}{1-z} \; dz.$$

Evaluation of $Y_1(n).$

Introduce $${2k\choose k} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{k+1}} (1+w)^{2k} \; dw.$$

With the Iverson bracket controlling the range we can extend $k$ to infinity to get for the sum $$\frac{2^n}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{\lfloor n/2\rfloor+1}} \frac{1}{1-z} \sum_{k\ge 0} 2^{-2k} z^k \frac{(1+w)^{2k}}{w^k} \; dz \; dw.$$

We can instantiate these contours to get convergence of the series. We thus obtain $$\frac{2^n}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{\lfloor n/2\rfloor+1}} \frac{1}{1-z} \frac{1}{1- z (1+w)^2 / w /4} \; dz \; dw \\ = \frac{2^{n+2}}{2\pi i} \int_{|w|=\epsilon} \frac{1}{(1+w)^2} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{\lfloor n/2\rfloor+1}} \frac{1}{z-1} \frac{1}{z- 4w/(1+w)^2} \; dz \; dw.$$

We evaluate the inner piece by computing the negative of the sum of the residues at $z=1,$ $z=4w/(1+w)^2$ and $z=\infty.$ We get for $z=1$ $$\frac{1}{1- 4w/(1+w)^2} = \frac{(1+w)^2}{(1+w)^2- 4w} = \frac{(1+w)^2}{(1-w)^2}$$ for a zero contribution.

We get for $z=\infty$ $$-\mathrm{Res}_{z=0} \frac{1}{z^2} \frac{1}{1/z^{\lfloor n/2\rfloor+1}} \frac{1}{1/z-1} \frac{1}{1/z- 4w/(1+w)^2} \\ = -\mathrm{Res}_{z=0} z^{\lfloor n/2\rfloor+1} \frac{1}{1-z} \frac{1}{1- 4wz/(1+w)^2}$$ again for a zero contribution.

Finally for $z=4w/(1+w)^2$ we get

$$-\frac{(1+w)^{2\lfloor n/2\rfloor+2}} {2^{2\lfloor n/2\rfloor+2} \times w^{\lfloor n/2\rfloor+1}} \frac{(1+w)^2}{(1-w)^2}.$$

Substitute into the outer integral to obtain $$-\frac{2^{n\mod 2}}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2\lfloor n/2\rfloor+2}} {w^{\lfloor n/2\rfloor+1}} \frac{1}{(1-w)^2} \; dw.$$

Extracting the negative of the residue we get the sum $$2^{n\mod 2}\sum_{q=0}^{\lfloor n/2\rfloor} {2\lfloor n/2\rfloor+2\choose q} (\lfloor n/2\rfloor-q+1).$$

This yields $$2^{n\mod 2} (\lfloor n/2\rfloor+1) \frac{1}{2} \left(2^{2\lfloor n/2\rfloor+2} - {2\lfloor n/2\rfloor+2\choose \lfloor n/2\rfloor+1} \right) \\ - 2^{n\mod 2} (2\lfloor n/2\rfloor+2) \sum_{q=1}^{\lfloor n/2\rfloor} {2\lfloor n/2\rfloor+1\choose q-1} \\ = 2^{n\mod 2} (\lfloor n/2\rfloor+1) \frac{1}{2} \left(2^{2\lfloor n/2\rfloor+2} - {2\lfloor n/2\rfloor+2\choose \lfloor n/2\rfloor+1} \right) \\ - 2^{n\mod 2} (\lfloor n/2\rfloor+1) \left(2^{2\lfloor n/2\rfloor+1} - 2{2\lfloor n/2\rfloor+1\choose \lfloor n/2\rfloor } \right) \\ = 2^{n\mod 2} (\lfloor n/2\rfloor+1) \left(2 - \frac{1}{2} \frac{2\lfloor n/2\rfloor+2}{\lfloor n/2\rfloor+1} \right) {2\lfloor n/2\rfloor+1\choose \lfloor n/2\rfloor } \\ = 2^{n\mod 2} (\lfloor n/2\rfloor+1) {2\lfloor n/2\rfloor+1\choose \lfloor n/2\rfloor }.$$

Evaluation of $Y_2(n).$

This is obviously very similar to the first case. We get the integral $$\frac{2^{n+1}}{2\pi i} \int_{|w|=\epsilon} \frac{1}{1+w} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{\lfloor (n-1)/2\rfloor+1}} \frac{1}{z-1} \frac{1}{z- 4w/(1+w)^2} \; dz \; dw.$$

There is no contribution from $z=1$ and $z=\infty$ as before which leaves $$-\frac{2^{(n+1)\mod 2}}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{2\lfloor (n-1)/2\rfloor+3}} {w^{\lfloor (n-1)/2\rfloor+1}} \frac{1}{(1-w)^2} \; dw.$$

Extracting the negative of the residue we obtain $$2^{(n+1) \mod 2} \sum_{q=0}^{\lfloor (n-1)/2\rfloor} {2\lfloor (n-1)/2\rfloor+3\choose q} (\lfloor (n-1)/2\rfloor-q+1).$$

This yields $$2^{(n+1) \mod 2} (\lfloor \frac{n-1}{2}\rfloor +1) \times \frac{1}{2} \left(2^{2\lfloor \frac{n-1}{2}\rfloor+3} - 2 {2\lfloor \frac{n-1}{2}\rfloor+3\choose \lfloor \frac{n-1}{2}\rfloor +1}\right) \\ - 2^{(n+1) \mod 2} (2\lfloor \frac{n-1}{2}\rfloor+3) \sum_{q=1}^{\lfloor \frac{n-1}{2}\rfloor} {2\lfloor \frac{n-1}{2}\rfloor+2 \choose q-1} \\ = 2^{(n+1) \mod 2} (\lfloor \frac{n-1}{2}\rfloor +1) \times \frac{1}{2} \left(2^{2\lfloor \frac{n-1}{2}\rfloor+3} - 2 {2\lfloor \frac{n-1}{2}\rfloor+3\choose \lfloor \frac{n-1}{2}\rfloor +1} \right) \\ - 2^{(n+1) \mod 2} (2\lfloor \frac{n-1}{2}\rfloor+3) \\ \times \frac{1}{2} \left(2^{2\lfloor \frac{n-1}{2}\rfloor+2} - 2{2\lfloor \frac{n-1}{2}\rfloor+2 \choose \lfloor \frac{n-1}{2}\rfloor} - {2\lfloor \frac{n-1}{2}\rfloor+2 \choose \lfloor \frac{n-1}{2}\rfloor+1} \right).$$

Evaluation of $Y(n).$

Keeping in mind that $Y(n)$ does not include a term for $k=0$ we get for $n = 2p$ the contributions

$$-2^{2p} + (p+1) {2p+1\choose p} + p \left(2^{2p+1} - 2 {2p+1\choose p}\right) \\ - (2p+1) \left(2^{2p} - 2 {2p\choose p-1} - {2p\choose p}\right) \\ = -2^{2p+1} + (4p+2){2p\choose p}.$$

On the other hand for $n = 2p+1$ we obtain $$-2^{2p+1} + 2 (p+1) {2p+1\choose p} + \frac{1}{2} (p+1) \left(2^{2p+3} - 2 {2p+3\choose p+1} \right) \\ - \frac{1}{2} (2p+3) \left(2^{2p+2} - 2{2p+2\choose p} - {2p+2\choose p+1}\right) \\ = -2^{2p+2} + (4p+5) {2p+1\choose p}.$$

Joining the two formulae we get the compact closed form $$-2^{n+1} + (2n + 2 + (n\mod 2)) {n\choose \lfloor n/2\rfloor}.$$

I would conjecture that with the closed form being this simple now that it has been computed we can probably find a much more elegant proof.

$\endgroup$
4
  • $\begingroup$ Does this match the computed values? $\endgroup$ Aug 10, 2015 at 4:05
  • $\begingroup$ In my CAS it does. $\endgroup$ Aug 10, 2015 at 4:06
  • $\begingroup$ Therefore, by the powers vested in me by me, I declare it proved! $\endgroup$ Aug 10, 2015 at 4:07
  • $\begingroup$ very much genius :) thx alot $\endgroup$
    – qwerty314
    Aug 12, 2015 at 21:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .