Semplifica un'espressione combinatoria che coinvolge $\binom{n}{[n/2]}$

Question

La mia domanda è se sia possibile semplificare

\ 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 *}

Questa espressione deriva da un vecchio problema della concorrenza di Harvard-MIT: si inizia con $n$ monete e lanciare ripetutamente una moneta, se mostra testa che guadagni $1$ moneta altrimenti perdi $1$moneta. Permettere$f(k)$ essere l'equilibrio dopo $k$lanci. Trova il valore atteso di$\max\{f(0),f(1),f(2),\cdots,f(2013)\}$. Ho scoperto che se$g(n,k)$ rappresenta il numero di modi per avere $k$ monete al massimo durante $n$lanci, quindi \ 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 *} e il valore atteso dipende solo da$g(n,0)$ che è uguale a $\binom{n}{[n/2]}$. Qualche idea? Sono curioso di sapere quanti studenti potrebbero effettivamente risolverlo in un lasso di tempo molto breve.

La soluzione ufficiale può essere trovata qui: (problema 10)

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

Answer 1

Con $\binom{x}{n}=\frac{1}{n!}\prod_{k=0}^{n-1}(x-k)$ esteso al reale $x$, si può provare (usando l'induzione su $n$, dì) $$\sum_{k=0}^n(-1)^k\binom{x}{k}=(-1)^n\binom{x-1}{n}.$$E noi abbiamo $2^{-k}\binom{k}{\lfloor k/2\rfloor}=a_{\lceil k/2\rceil}$ con $a_n=(-1)^n\binom{-1/2}{n}$ (facile da controllare separatamente per dispari / pari $k$).

Da $\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$, la nostra somma è uguale $\color{blue}{S_{\lfloor n/2\rfloor}+S_{\lceil n/2\rceil}-1}$ con $$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}.$$

(Inizialmente ho usato la generazione di funzioni; una serie di semplificazioni ha portato a quanto sopra.)