# What is $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$?

Since both $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor$ and $\sum_{i=0}^n \binom{n}{i}$ have simple closed-form evaluations, it is natural to consider the evaluation of the binomial sum $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$.

The integer sequence $$\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)$$ is not currently in the On-Line Encyclopedia of Integer Sequences, and it is not obvious as to how to construct a closed-form evaluation of this sequence.

Is there a combinatorial or bijective way of approaching the problem of evaluating $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$? What does $\sum_{i=0}^n \left\lfloor \sqrt{i}\right\rfloor \binom{n}{i}$ count? Is there a natural inductive proof for evaluating this sum?

• Well, $f(n+1)-2f(n)$ looks mighty like oeis.org/A103198. Jun 28, 2016 at 18:10

Let $f(n)=\sum_{i=0}^{n}{\lfloor\sqrt i\rfloor\binom{n}{i}}$ and $f(0)=0$.
We have: $$\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}}$$ And thus: $$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}}$$ Now define $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\}$ i.e. the set of all ordered partitions of $n$ into a square number of parts (we define $P_0=\emptyset$). If $i≤\lfloor\sqrt n\rfloor$ then the number of partitions of $n$ into $i^2$ parts can be determined as follows:
We initiate the $i^2$-tuple $\left(x_1,...,x_{i^2}\right)$ to $\left(1,...,1\right)$. Now we draw randomly one of the first $i^2$ natural numbers, say $j$, and increase $x_j$ by $1$. After that, we put the number $j$ back in the bowl and start again. After doing this $n-i^2$ times, the sum of the $x_j$ is equal to $n$ and we easily see that with this procedure the number of such tuples is just the number of unordered $n-i^2$ tuples formed by the integers $1,...,i^2$. This number is known to be $\binom{i^2+\left(n-i^2\right)-1)}{n-i^2}=\binom{n-1}{n-i^2}=\binom{n-1}{i^2-1}$. So we can deduce: $$\left|P_n\right|=\sum_{i=1}^{\lfloor n\rfloor}{\binom{n-1}{i^2-1}}=f(n)-2f(n-1)$$ So, if you accept $\left|P_n\right|$ to appear in the closed form (which corresponds to oeis.org/A103198 as mentioned by Ivan Neretin) of the sum, we have: $$f(n)=\sum_{i=1}^n{2^{n-i}\left|P_i\right|}$$ Note:
To justify the "usefulness" of this identity: it allows us to calculate the generating function of $f$. We can see from the definition of $P_n$ that: $$\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$$ Where $\vartheta_3\left(x\right)=\vartheta_3\left(0,x\right)$ is a jacobi theta function. With Cauchys product formula this gives: $$\sum_{k=0}^{\infty}{f(k)x^k}=\frac{1}{1-2x}\cdot\frac{\vartheta_3\left(\frac{x}{1-x}\right)-1}{2}$$