Crecimiento de la recurrencia binomial modificada

Question

Los coeficientes binomiales $\binom{n}{r}$ satisface $\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$ . Esto significa que es una solución de la ecuación $f(n,r)=f(n-1,r)+f(n-1,r-1)$ con condiciones iniciales $f(n,0)=1$ para $n\geq 0$ y $f(0,r)=0$ para $r>0$ .

¿Y si cambiamos ligeramente la recurrencia a $f(n,r)=f(n-\textbf{2},r)+f(n-1,r-1)$ ? ¿El crecimiento asintótico seguirá siendo el mismo que el de los coeficientes binomiales? Si no, ¿cuál será? (Si las condiciones iniciales importan, supongamos que $f(n,r)=1$ si no puede ser definido por la recurrencia).

Answer 1

Si se utilizan las mismas condiciones iniciales que los coeficientes binomiales, se obtiene la fórmula $$ f(n,r) = \binom{\lfloor \frac{n+r}{2} \rfloor}{r}, $$ del que se puede extraer la asintótica.

Un dato curioso: $\sum_{r=0}^n f(n,r) = F_{r+2}$ , donde $F_r$ es el $r$ El número de Fibonacci.