# Double Binomial Sum

I've been tackling the following problem from Concrete Mathematics (Graham et al., chapter 5).

I turned to the answers at some point -- which alas, I have trouble understanding!

Can you provide an answer that elaborates most important steps. For example how is floor-square op replaced by factor $$2 \ k + 1$$ and loosened constraint on $$j$$?

First, replace $$k-j$$ by $$\ell$$,

Summing over all integers $$0\le j \le k$$ is the same as summing over integers $$0\le j$$ and $$0\le \ell$$, where $$\ell$$ is serving the role of $$k-j$$. The result is

$$\sum_{j,\ell\ge 0} \binom{-1}{j-\lfloor\sqrt{ \ell} \rfloor}\binom{j}m \frac1{2^j}$$

then replace $$\lfloor \sqrt \ell \rfloor$$ by $$k$$.

As $$\ell$$ ranges over positive integers, the quantity $$\lfloor \sqrt \ell \rfloor$$ does as well, except that the value of $$k$$ is attained a total of $$2k+1$$ times. For example, there are $$5$$ numbers whose square root rounded down is $$2$$, and those are $$4,5,6,7,8$$. In this step, we collect all these repeated terms in to one term; the $$k$$ represents the square root, and $$2k+1$$ is the number of $$\ell$$ which make that square root.

Now, sum over $$k$$,

Ignoring terms which do not depend on $$k$$, the summation over $$k$$ looks like $$\sum_{k} \binom{-1}{j-k} (2k+1) = (2j+1)-(2j-1)+(2j-3)-\dots\pm 1$$ In words, since $$\binom{-1}{j-k}=(-1)^{j-k}$$ whenever $$j-k\ge 0$$, and $$0$$ otherwise, this summation is the alternating sum of the first $$j+1$$ odd numbers. A little thought shows that this sum is equal to $$j+1$$; one way to prove this is to break into cases based on whether $$j$$ is even or odd, then perform all of the adjacent subtractions, leaving a sum of $$\lfloor j/2\rfloor$$ two's.

Absorb the $$j+1$$ and apply $$(5.57)$$.

I think you can take it from here? The absorption identity is $$\binom{n}k(n+1)=\binom{n+1}{k+1}(k+1)$$.

• This makes everything clear. I wish I hadn't been intimidated by the whole problem. It's not that hard to proceed once you think well about the index domains.
– BoLe
Commented Dec 25, 2018 at 13:50