4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ $$\lim\frac{f(n)}{2^n\sqrt{n}}=\frac1{\sqrt{2}}$$ $\endgroup$ – Did Jun 29 '16 at 11:43
  • $\begingroup$ @Did can you prove that? $\endgroup$ – Redundant Aunt Jun 29 '16 at 12:10
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Did Jun 29 '16 at 12:41
  • $\begingroup$ Ingenious! But why in comment form? $\endgroup$ – Redundant Aunt Jun 29 '16 at 12:59
  • $\begingroup$ To let you the option of expanding this sketch into a full solution and of posting it below as an answer, probably. $\endgroup$ – Did Jul 2 '16 at 8:15
-1
$\begingroup$

$\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.

$\endgroup$
  • $\begingroup$ Let's agree that there is a much better answer in the comments below the question! $\endgroup$ – Alex M. Jul 19 '16 at 19:52
  • $\begingroup$ @AlexM. I agree completely with you. This is closer to a hint or some suggestion to be picked up by some clever user. Thanks a lot for your remark. $\endgroup$ – Felix Marin Jul 19 '16 at 20:50

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.