Simplifier une expression combinatoire impliquant $\binom{n}{[n/2]}$

Question

Ma question est de savoir s'il est possible de simplifier

\ 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 {équation *}

Cette expression vient d'un vieux problème de compétition Harvard-MIT: vous commencez par $n$ pièces et lancez une pièce à plusieurs reprises, si elle montre des têtes que vous gagnez $1$ pièce sinon vous perdez $1$pièce de monnaie. Laisser$f(k)$ être l'équilibre après $k$lancers. Trouvez la valeur attendue de$\max\{f(0),f(1),f(2),\cdots,f(2013)\}$. J'ai trouvé que si$g(n,k)$ représente le nombre de façons d'avoir $k$ pièces maximales pendant $n$lancers, puis \ begin {équation *} g (n, k) = g (n-1, k-1) + g (n-1, k + 1) \; \; \ text {pour} \; \; k \ geq 1; \ quad g (n, 0) = g (n-1,0) + g (n-1,1) \ end {équation *} et la valeur attendue ne dépend que de$g(n,0)$ qui est égal à $\binom{n}{[n/2]}$. Une idée? Je suis curieux de savoir combien d'élèves pourraient y parvenir en très peu de temps.

La solution officielle peut être trouvée ici: (problème 10)

https://hmmt-archive.s3.amazonaws.com/tournaments/2013/feb/comb/solutions.pdf

Answer 1

Avec $\binom{x}{n}=\frac{1}{n!}\prod_{k=0}^{n-1}(x-k)$ étendu au réel $x$, on peut prouver (en utilisant l'induction sur $n$, dire) $$\sum_{k=0}^n(-1)^k\binom{x}{k}=(-1)^n\binom{x-1}{n}.$$Et nous avons $2^{-k}\binom{k}{\lfloor k/2\rfloor}=a_{\lceil k/2\rceil}$ avec $a_n=(-1)^n\binom{-1/2}{n}$ (facile à vérifier séparément pour impair / pair $k$).

Depuis $\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$, notre somme est égale $\color{blue}{S_{\lfloor n/2\rfloor}+S_{\lceil n/2\rceil}-1}$ avec $$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}.$$

(J'ai utilisé des fonctions de génération au départ; une série de simplifications a conduit à ce qui précède.)