# Simplify a combinatorial expression involving $\binom{n}{[n/2]}$

My question is whether it is possible to simplify

$$\begin{equation*} \sum_{k=0}^n \frac{\binom{k}{[k/2]}}{2^k}=\frac{\binom{0}{0}}{1}+\frac{\binom{1}{0}}{2}+\frac{\binom{2}{1}}{4}+\frac{\binom{3}{1}}{8}\cdots \end{equation*}$$

This expression comes from an old Harvard-MIT competition problem: you start with $$n$$ coins and repeatedly flip a coin, if it shows heads you gain $$1$$ coin otherwise you lose $$1$$ coin. Let $$f(k)$$ be the balance after $$k$$ tossings. Find the expected value of $$\max\{f(0),f(1),f(2),\cdots,f(2013)\}$$. I found that if $$g(n,k)$$ represents the number of ways to have $$k$$ coins maximal during $$n$$ tossings, then $$\begin{equation*} g(n,k)=g(n-1,k-1)+g(n-1,k+1) \;\;\text{for}\;\;k\geq 1;\quad g(n,0)=g(n-1,0)+g(n-1,1) \end{equation*}$$ and the expected value only depends on $$g(n,0)$$ which equals $$\binom{n}{[n/2]}$$. Any idea? I am curious how many students could actually work it out in a very short amount of time.

The official solution can be found here: (problem 10)

https://hmmt-archive.s3.amazonaws.com/tournaments/2013/feb/comb/solutions.pdf

With $$\binom{x}{n}=\frac{1}{n!}\prod_{k=0}^{n-1}(x-k)$$ extended to real $$x$$, one can prove (using induction on $$n$$, say) $$\sum_{k=0}^n(-1)^k\binom{x}{k}=(-1)^n\binom{x-1}{n}.$$ And we have $$2^{-k}\binom{k}{\lfloor k/2\rfloor}=a_{\lceil k/2\rceil}$$ with $$a_n=(-1)^n\binom{-1/2}{n}$$ (easy to check separately for odd/even $$k$$).
Since $$\sum_{k=0}^n b_{\lceil k/2\rceil}=\sum_{k=0}^{\lfloor n/2\rfloor}b_k+\sum_{k=1}^{\lceil n/2\rceil}b_k$$, our sum equals $$\color{blue}{S_{\lfloor n/2\rfloor}+S_{\lceil n/2\rceil}-1}$$ with $$S_n=\sum_{k=0}^{n}(-1)^k\binom{-1/2}{k}=(-1)^n\binom{-3/2}{n}=\frac{2n+1}{2^{2n}}\binom{2n}{n}.$$
• Thanks a lot, metamorphy! I checked your calculation and for even $n$, the sum equals $(n+1)2^{1-n}\binom{n}{n/2}-1$; for odd $n$, it equals $(2n+3)2^{-1-n}\binom{n+1}{(n+1)/2}-1$. They are correct for $0\leq n\leq 5$. The original problem should have answer equal to half of the sum for $n=2013$, but the official answer is different. If $(2n+3)$ is replaced by $2n+2$ then they match. – Haoran Chen Aug 26 '20 at 8:58
• Sorry @metamorphy my previous comment was wrong. The correct answer is to take half of the sum at $n=2012$. Now it works. – Haoran Chen Aug 26 '20 at 9:31