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)



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

  • $\begingroup$ 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. $\endgroup$ – Haoran Chen Aug 26 '20 at 8:58
  • $\begingroup$ Sorry @metamorphy my previous comment was wrong. The correct answer is to take half of the sum at $n=2012$. Now it works. $\endgroup$ – Haoran Chen Aug 26 '20 at 9:31

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.