Messy sum simplifies to a binomial coefficient!

Relevant wiki: Double Counting

Here, we make use of the double counting technique:

Consider a team, which has $n$ males, $n$ females and $1$ leader. The number of combinations of $n$ people in total showing up in an event can be counted in two different ways:

$(1).$ Since this is equivalent to choosing $n$ elements from $n+n+1=2n+1$ elements, the number of combinations can be expressed as $\binom{2n+1}{n}$ .

$(2).$ Let the $n$ males and $n$ females form $n$ pairs of couples. Then among the $n$ people who show up, some people's partners might be absent. Let the number of people whose partners are absent be $i$ , with $0\leqslant i\leqslant n$ .

First, choose the couples containing the $i$ people whose partners are missing. Since there are a total of $n$ couples, we can do this in $\binom{n}{i}$ ways. Then choose one person from each couple to show up, which can be done in $2^{i}$ ways. Therefore, there are $2^{i}\binom{n}{i}$ number of ways to choose the $i$ people with missing partners.

Next, choose the couples who do show up (i.e. each person's partner is not missing). Let the number of couples who do show up be $k$ . Then, consider two situations, namely, when the leader shows up and when the leader doesn't show up. If the leader shows up, then $2k+1+i=n$ , giving $k=\frac{n-i-1}{2}$ . If the leader doesn't show up, then $2k+i=n$ , giving $k=\frac{n-i}{2}$ . Either way, $k=\left \lfloor (n-i)/2 \right \rfloor$ .

Since we've already selected $i$ people with absent partners, we only have $n-i$ potential couples to show up. The number of ways of choosing $k$ couples from these $n-i$ potential couples is therefore $\binom{n-i}{k}=\binom{n-i}{\left \lfloor (n-i)/2 \right \rfloor}$ .

Summing over $0\leqslant i\leqslant n$ , we have the result

$\sum_{i=0}^n 2^i{n\choose i}{n-i\choose \left\lfloor\frac{n-i}{2}\right\rfloor}=\binom{2n+1}{n}.$

Thus, $M=2 \times 2017+1= \boxed{4035}.$