# Messy sum simplifies to a binomial coefficient!

Probability Level 5

Let $S(n)=\sum_{i=0}^n 2^i{n\choose i}{n-i\choose \left\lfloor\frac{n-i}{2}\right\rfloor}.$

If $S(2017) = \dbinom{M}{2017}$, find $M$.


Notations:

• $\lfloor \cdot \rfloor$ denotes the floor function.
• $\dbinom MN = \dfrac {M!}{N! (M-N)!}$ denotes the binomial coefficient.

×