Double Binomial Sum

Question

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

Answer 1

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)$.