Simple pero interesante problema sobre el coeficiente binomial de la Olimpiada

Question

"Definamos $a_n=\sum\limits_{k=0}^{\lfloor n/2 \rfloor} {n-k \choose k}\left(-\frac{1}{4}\right)^k$ . Evaluar $a_{1997}$ ."

Este problema es de la ronda final de una antigua Olimpiada Matemática de Corea del Sur (KMO 1997).
Creo que este problema es muy sencillo, pero requiere algunas ideas combinatorias, y además es muy interesante.
Pero como ha pasado mucho tiempo, no encuentro ninguna solución o guía al respecto.
Traté de dividir la forma explícita de $(x+y)^{2k}$ con $x^k$ pero no funciona bien.
¿Me ayudarías?

Answer 1

Aceite de serpiente: \begin{align} \sum_{n=0}^\infty a_n z^n &= \sum_{n=0}^\infty \left(\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}\left(-\frac{1}{4}\right)^k \right) z^n \\ &= \sum_{k=0}^\infty \left(-\frac{1}{4}\right)^k\sum_{n=2k}^\infty \binom{n-k}{k} z^n \\ &= \sum_{k=0}^\infty \left(-\frac{1}{4}\right)^k z^{2k}\sum_{n=0}^\infty \binom{n+k}{k} z^n \\ &= \sum_{k=0}^\infty \left(-\frac{z^2}{4}\right)^k\frac{1}{(1-z)^{k+1}} \\ &= \frac{1}{1-z}\sum_{k=0}^\infty \left(-\frac{z^2}{4(1-z)}\right)^k \\ &= \frac{1}{1-z}\cdot\frac{1}{1+\frac{z^2}{4(1-z)}} \\ &= \frac{1}{(1-z/2)^2} \\ &= \sum_{n=0}^\infty \binom{n+1}{1} (z/2)^n \\ &= \sum_{n=0}^\infty \frac{n+1}{2^n} z^n \end{align} Así que $a_n= (n+1)/2^n$ para $n \ge 0$ .

Answer 2

Se trata de una solución que supone una experiencia en la resolución de recurrencias lineales homogéneas. Tal vez haya una solución más elemental o inteligente que se pretendía, pero no la imagino. \begin{aligned} a_n &=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}(-1/4)^k \\&=\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k-1}{k}(-1/4)^{k}+\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k-1}{k-1}(-1/4)^k \\&=\sum_{k=0}^{\lfloor n/2\rfloor}\binom{(n-1)-k}{k}(-1/4)^k+(-1/4)\sum_{k=0}^{\lfloor n/2\rfloor}\binom{(n-2)-(k-1)}{k-1}(-1/4)^{k-1} \\&=a_{n-1}-(1/4)a_{n-2} \end{aligned} Puede que se queje del último paso, ya que la definición $a_{n-1}$ requiere que la suma vaya a $\lfloor (n-1)/2\rfloor$ y $a_{n-2}$ requiere que la suma vaya a $\lfloor (n-2)/2\rfloor$ pero ambos límites superiores son $\lfloor n/2\rfloor$ . Esto significa que la primera suma tiene cero o un término extra, dependiendo de la paridad de $n$ mientras que el segundo tiene un término más. Puedes comprobar que ambos términos extra son cero, por lo que no hay problema.

Se trata de una recurrencia lineal homogénea con polinomio característico $x^2-x+1/4=(x-1/2)^2$ . Por lo tanto, la solución general es $$a_n=(Cn+D)(1/2)^n.$$ Desde $a_0=a_1=1$ puede resolver para $C$ y $D$ para encontrar $D=1$ y $C=1$ . Por lo tanto, $$ a_n=(n+1)/2^n. $$