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}.$$
(I used generating functions initially; a series of simplifications led to the above.)