Биномиальное тождество

[Dave]

Докажите, что для любых неотрицательных целых $m$ и $n$ выполняется тождество

$$\sum_{k=m}^{\lfloor m+\frac n 2 \rfloor}{\binom k m \binom {2m+n+1} {2k+1}}=2^n \binom {m+n} m.$$

[TOTAL]

$$\sum_{0 \le 2k \le n}C_{m+k}^k C_{2m+n+1}^{n-2k}= \sum_{0 \le k \le n}C_{m+k}^k C_{m+n}^{n-k}=2^nC_{m+n}^n$$

Первое равенство получается сравнением коэф-та перед $x^n$ в

$$(1+x)^{2m+n+1} (1-x^2)^{-m-1}=(1+x)^{m+n} (1-x)^{-m-1}$$

Второе равенство получается сравнением коэф-та перед $x^m$ в

$$(2+x)^{m+n} =(1+(1+x))^{m+n}$$

[Dave]

Это тождество также дает один из вариантов решения следующей задачи.

Петя подбрасывает монету и ведёт счёт решек следующим оригинальным способом. Вначале он пишет на доске число $1$. После выпадения каждой следующей пары решек (не обязательно подряд) он увеличивает это число в $5$ раз. Пусть $\xi_n$ - число, записанное на доске после $n$ подбрасываний монеты. Докажите, что

$$M \xi_n=M \xi_{n-1}+M \xi_{n-2}.$$