¿Qué es? $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$ ?

Question

Dado que ambos $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor$ y $\sum_{i=0}^n \binom{n}{i}$ tienen evaluaciones simples de forma cerrada, es natural considerar la evaluación de la suma binomial $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$ .

La secuencia de números enteros $$\left( \sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i} : n \in \mathbb{N} \right) = \left( 1, 3, 7, 16, 37, 85, 191, 418, 894, 1882, \cdots \right)$$ no está actualmente en la Enciclopedia On-Line de Secuencias de Números Enteros, y no es obvio cómo construir una evaluación de forma cerrada de esta secuencia.

¿Existe una forma combinatoria o biyectiva de abordar el problema de evaluar $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$ ? ¿Qué hace $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$ ¿contar? ¿Existe una prueba inductiva natural para evaluar esta suma?

Answer 1

Aquí hay una prueba del comentario de Ivan Neretin:

Dejemos que $f(n)=\sum_{i=0}^{n}{\lfloor\sqrt i\rfloor\binom{n}{i}}$ y $f(0)=0$ .

Lo tenemos: $$ \sum_{i=0}^{n+1}{\lfloor\sqrt i\rfloor\binom{n+1}{i}}=\sum_{i=0}^{n+1}{\lfloor\sqrt i\rfloor\left(\binom{n}{i-1}+\binom{n}{i}\right)}=\sum_{i=0}^n{\lfloor\sqrt {i+1}\rfloor\binom{n}{i}}+\sum_{i=0}^n{\lfloor\sqrt {i}\rfloor\binom{n}{i}} $$ Y así: $$ f(n+1)-2f(n)=\sum_{i=0}^n{\left(\lfloor\sqrt {i+1}\rfloor-\lfloor\sqrt {i}\rfloor\right)\binom{n}{i}}=\sum_{i=1}^{\lfloor\sqrt{n+1}\rfloor}{\binom{n}{i^2-1}} $$ Ahora defina $P_n=\{\left(x_1,...,x_{i^2}\right)\mid i\in\mathbb{N},\ x_1,...,x_{i^2}\in\mathbb{N},\ n=\sum_{k=1}^{i^2}x_k\}$ es decir, el conjunto de todas las particiones ordenadas de $n$ en un número cuadrado de partes (definimos $P_0=\emptyset$ ). Si $i≤\lfloor\sqrt n\rfloor$ entonces el número de particiones de $n$ en $i^2$ las partes pueden determinarse de la siguiente manera:

Iniciamos el $i^2$ -tupla $\left(x_1,...,x_{i^2}\right)$ a $\left(1,...,1\right)$ . Ahora extraemos al azar uno de los primeros $i^2$ números naturales, digamos $j$ y aumentar $x_j$ por $1$ . Después de eso, ponemos el número $j$ de nuevo en el bol y empezar de nuevo. Después de hacer esto $n-i^2$ veces, la suma de los $x_j$ es igual a $n$ y vemos fácilmente que con este procedimiento el número de tales tuplas es simplemente el número de tuplas desordenadas $n-i^2$ tuplas formadas por los enteros $1,...,i^2$ . Se sabe que este número es $\binom{i^2+\left(n-i^2\right)-1)}{n-i^2}=\binom{n-1}{n-i^2}=\binom{n-1}{i^2-1}$ . Así que podemos deducir: $$ \left|P_n\right|=\sum_{i=1}^{\lfloor n\rfloor}{\binom{n-1}{i^2-1}}=f(n)-2f(n-1) $$ Así que, si acepta $\left|P_n\right|$ para aparecer en la forma cerrada (que corresponde a oeis.org/A103198 como menciona Ivan Neretin) de la suma, tenemos: $$ f(n)=\sum_{i=1}^n{2^{n-i}\left|P_i\right|} $$ Nota:

Para justificar la "utilidad" de esta identidad: nos permite calcular la función generadora de $f$ . Podemos ver en la definición de $P_n$ eso: $$ \frac{\vartheta_3\left(\frac{x}{1-x}\right)-1}{2}=\sum_{k=1}^{\infty}{\left(\frac{x}{1-x}\right)^{k^2}}=\sum_{k=0}^{\infty}{\left|P_k\right|}x^k $$ Donde $\vartheta_3\left(x\right)=\vartheta_3\left(0,x\right)$ es una función jacobi theta. Con la fórmula del producto de Cauchys esto da: $$ \sum_{k=0}^{\infty}{f(k)x^k}=\frac{1}{1-2x}\cdot\frac{\vartheta_3\left(\frac{x}{1-x}\right)-1}{2} $$