2
$\begingroup$

Where the thing that looks like a floor function is the floor function. This is an interesting result which I hoped to prove by induction, but ran into trouble applying the inductive hypothesis. The base case is trivial. Here's the progress I made:

Inductive hypothesis: $\sum_{k=0}^m 2^k \binom{m}{k} \binom{m-k}{\lfloor{(m-k)/2}\rfloor}=\binom{2m+1}{m}$ for some $m>0$. Then \begin{align*} &\sum_{k=0}^{m+1} 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}\\ =&\sum_{k=0}^m 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}+2^{m+1} \binom{m+1}{m+1} \binom{m+1-m+1}{\lfloor{(m+1-(m+1))/2}\rfloor}\\ =&2^{m+1}+\sum_{k=0}^m 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor} \end{align*} Let $A$ be the set of all $k\in[0,m]$ such that $m+1-k$ is even. Let $B$ be the set of $k\in[0,m]$ such that $m+1-k$ is odd. Observe that for each $k\in[0,m]$, $k$ is in exactly one of $A$ or $B$. It follows that \begin{align*} &\sum_{k=0}^m 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}\\ =&\sum_{k\in A} 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}+\sum_{k\in B} 2^k \binom{m+1}{k} \binom{m+1-k}{\lfloor{(m+1-k)/2}\rfloor}\\ =&\sum_{k\in A} 2^k \binom{m+1}{k} \binom{m+1-k}{(m+1-k)/2}+\sum_{k\in B} 2^k \binom{m+1}{k} \binom{m+1-k}{(m-k)/2} \end{align*}

Splitting the sum into $A$ and $B$ was a last-ditch attempt to form the expression into something to which I could apply the inductive hypothesis. Did I make a mistake somewhere, is this the wrong approach, or am I just missing the next step?

$\endgroup$
3
$\begingroup$

There are $ 2n+1 \choose n $ strings consisting of $n$ ones and $n+1$ zeroes.

Given any such string $S$, let $S_1$ consist of the first $n$ digits of the string $S$ and let $S_2$ consist of the last $n+1$ digits of $S$. Suppose that there $k$ values of $i$ such that the $i^{th}$ element of $S_1$ is different from the $i^{th}$ element of $S_2$. Then there are $n \choose k$ ways to choose which digits $i$ the two strings differ at. There are $2^k$ ways to assign these $k$ elements in $S_1$.

Now consider the number of ways in which the rest of the elements may be chosen. We need to choose the remaining $n-k$ elements of $S_1$ (which are the same as their respective elements in $S_2$) and the last element of $S_2$. The number of zeroes must be one greater than the number of ones. It can be shown that the number of ways to do this is $n-k \choose \lfloor\frac{n-k}{2}\rfloor$.

$\endgroup$
2
$\begingroup$

Seeking to verify

$$\sum_{k=0}^n 2^k {n\choose k} {n-k\choose \lfloor (n-k)/2 \rfloor} = {2n+1\choose n}$$

we observe that

$${n\choose k} {n-k\choose \lfloor (n-k)/2 \rfloor} = \frac{n!}{k! \times \lfloor (n-k)/2 \rfloor! \times (n-k-\lfloor (n-k)/2 \rfloor)!} \\ = {n\choose \lfloor (n-k)/2 \rfloor} {n-\lfloor (n-k)/2 \rfloor \choose n-k-\lfloor (n-k)/2 \rfloor}.$$

We get

$$2^n \sum_{k=0}^n 2^{-k} {n\choose \lfloor k/2 \rfloor} {n- \lfloor k/2 \rfloor \choose k - \lfloor k/2 \rfloor}.$$

This yields two pieces:

$$2^n \sum_{q=0}^{\lfloor n/2 \rfloor} 2^{-2q} {n\choose q} {n- q \choose q}$$

and

$$2^n \sum_{q=0}^{\lfloor (n-1)/2 \rfloor} 2^{-2q-1} {n\choose q} {n- q \choose q+1}.$$

We write for the first one

$$2^n \sum_{q=0}^{\lfloor n/2 \rfloor} 2^{-2q} {n\choose q} {n- q \choose n-2q} \\ = 2^n \sum_{q=0}^{\lfloor n/2 \rfloor} 2^{-2q} {n\choose q} [z^{n-2q}] (1+z)^{n-q} \\ = 2^n [z^n] (1+z)^n \sum_{q=0}^{\lfloor n/2 \rfloor} 2^{-2q} {n\choose q} z^{2q} (1+z)^{-q}.$$

Now the coefficient extractor enforces the upper limit of the sum and we find

$$2^n [z^n] (1+z)^n \sum_{q\ge 0} 2^{-2q} {n\choose q} z^{2q} (1+z)^{-q} \\ = 2^n [z^n] (1+z)^n \left(1+\frac{1}{2^2}\frac{z^2}{1+z}\right)^n = 2^n [z^n] \left(1 + z + \frac{1}{2^2} z^2\right)^n \\ = 2^n [z^n] \left(1 + \frac{1}{2} z\right)^{2n} = {2n\choose n}.$$

The second one is of course very similiar:

$$2^n \sum_{q=0}^{\lfloor (n-1)/2 \rfloor} 2^{-2q-1} {n\choose q} {n- q \choose n-2q-1} \\ = 2^n \sum_{q=0}^{\lfloor (n-1)/2 \rfloor} 2^{-2q-1} {n\choose q} [z^{n-2q-1}] (1+z)^{n-q} \\ = 2^n [z^{n-1}] (1+z)^n \sum_{q=0}^{\lfloor (n-1)/2 \rfloor} 2^{-2q-1} {n\choose q} z^{2q} (1+z)^{-q}.$$

Once more the coefficient extractor enforces the upper limit of the sum and we find

$$2^{n-1} [z^{n-1}] (1+z)^n \sum_{q\ge 0} 2^{-2q} {n\choose q} z^{2q} (1+z)^{-q} \\ = 2^{n-1} [z^{n-1}] (1+z)^n \left(1+\frac{1}{2^2}\frac{z^2}{1+z}\right)^n = 2^{n-1} [z^{n-1}] \left(1 + z + \frac{1}{2^2} z^2\right)^n \\ = 2^{n-1} [z^{n-1}] \left(1 + \frac{1}{2} z\right)^{2n} = {2n\choose n-1}.$$

Adding the two binomial coefficients we indeed obtain

$$\bbox[5px,border:2px solid #00A000]{ {2n+1\choose n}.}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.