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?


1 Answer 1


Here is a proof of the comment by Ivan Neretin:

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} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.