# Asymptotic vlaue of $f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i}$

Inspired by this question I tried to find an asymptotic formula for $$f(n)=\sum_{i=0}^n\lfloor \sqrt{i}\rfloor\binom{n}{i}$$ With the observation: $$f(n)=\sum_{i=0}^n\frac{\lfloor \sqrt{i}\rfloor+\lfloor \sqrt{n-i}\rfloor}{2}\binom{n}{i}$$ And the a bit naive approximation $$\frac{\lfloor \sqrt{i}\rfloor+\lfloor \sqrt{n-i}\rfloor}{2}=\frac{1}{n}\sum_{i=1}^{n}{\lfloor \sqrt{i}\rfloor}=\frac{n\lfloor \sqrt{n}\rfloor-\frac{1}{6}\lfloor \sqrt{n}\rfloor\left(\lfloor \sqrt{n}\rfloor-1\right)\left(2\lfloor \sqrt{n}\rfloor+5\right)}{n}\approx\frac{2}{3}\sqrt{n}$$ We obtain $f(n)\approx\frac{2}{3}\sqrt{n}2^n=:g(n)$. The approximation doesn't seem that bad; I computed with wolfram alpha:  \begin{array}{c|c|c|c} n & f(n) & g(n) & f(n)/g(n) \\ \hline 1 & 1 & 1.333 & 0.75 \\ 2 & 3 & 3.771 & 0.795 \\ 3 & 7 & 9.238 & 0.758 \\ 4 & 16 & 21.333 & 0.75 \\ 5 & 37 & 47.703 & 0.776 \\ 10 & 1882 & 2158.782 & 0.872 \\ 50 & 5.128\cdot10^{15} & 5.308\cdot10^{15} & 0.996 \\ 100 & 8.391\cdot10^{30} & 8.451\cdot10^{30} & 0.993 \\ 200 & 1.531\cdot10^{61} & 1.515\cdot10^{61} & 1.011 \\ 350 & 2.929\cdot10^{106} & 2.86\cdot10^{106} & 1.024 \\ \end{array}  The error term fluctuates a bit so it seems natural to ask:

Is it true that: $$\lim_{n\to\infty}{\frac{f(n)}{g(n)}}=1$$

• $$\lim\frac{f(n)}{2^n\sqrt{n}}=\frac1{\sqrt{2}}$$ – Did Jun 29 '16 at 11:43
• @Did can you prove that? – Redundant Aunt Jun 29 '16 at 12:10
• Yes. Ingredients are that, for every positive $a$, there exists some $b<2$ such that $$\sum_{i\in I_n(a)}{n\choose i}\sim2^n,\qquad\sum_{i\notin I_n(a)}{n\choose i}\leqslant b^n,$$ where $$I_n(a)=\left[\tfrac12(1-a)n,\tfrac12(1+a)n\right],$$ and the fact that $\lfloor\sqrt{i}\rfloor\leqslant\sqrt{n}$ for every $i$ in $[0,n]$ and that $$\sqrt{(1-a)n/2}\leqslant\lfloor\sqrt{i}\rfloor\leqslant\sqrt{(1+a)n/2}$$ for every $i$ in $I_n(a)$. – Did Jun 29 '16 at 12:41
• Ingenious! But why in comment form? – Redundant Aunt Jun 29 '16 at 12:59
• To let you the option of expanding this sketch into a full solution and of posting it below as an answer, probably. – Did Jul 2 '16 at 8:15

$\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \color{#f00}{\mathrm{f}\pars{n}} & =\sum_{k = 0}^{n}\left\lfloor \root{k}\right\rfloor{n \choose k}\ =\ 1\times\overbrace{\bracks{{n \choose 1} + {n \choose 2} + {n \choose 3}}} ^{\ds{\color{#f00}{3}\ terms}} \\[3mm] & + 2 \times\overbrace{\bracks{{n \choose 4} + {n \choose 5} + {n \choose 6} + {n \choose 7} + {n \choose 8}}} ^{\ds{\color{#f00}{5}\ terms}} \\[3mm] & + 3 \times\overbrace{\bracks{{n \choose 9} + {n \choose 10} + {n \choose 11} + {n \choose 12} + {n \choose 13}+ {n \choose 14}+ {n \choose 15}}} ^{\ds{\color{#f00}{7}\ terms}}\ +\ \cdots \\[5mm] &= 1 \times \sum_{k = 1}^{3}{n \choose k} + 2 \times \sum_{k = 4}^{8}{n \choose k} + 3 \times \sum_{k = 9}^{15}{n \choose k} + \cdots \\[3mm] & = \sum_{m = 1}^{\infty}m\sum_{k = m^{2}}^{m^{2} + 2m}{n \choose k} = \sum_{m = 0}^{\infty}m\sum_{k = 0}^{2m}{n \choose k + m^{2}} = \sum_{k = 0}^{\infty}\sum_{m\ \geq\ k/2}^{\infty}m{n \choose k + m^{2}} \end{align}
I stop here. Some of the binomial sum seems to be related to Hypergeometric Functions. So far, I was able to get rid of the $\ds{\left\lfloor\cdots\right\rfloor}$ function and along the way to find a pattern.