0

Q: Find a formula for $\sum_{k=0}^m⌊\sqrt{k}⌋$, when m is a positive integer.

I checked the answer, and it is

$\frac{n(n+1)(2n+1)}{3}+\frac{n(n+1)}{2}+(n+1)(m-(n+1)^2+1)$, where $n=⌊\sqrt{m}⌋-1$.

I am currently studying discrete mathematics by myself, and I have no idea how to solve this question. Please provide me some extra explanations to the answer.

Thank you in advance.

RobPratt
  • 45,619
Eric
  • 135
  • Graphically, that sum is counting integer points under the curve $y=\sqrt{x}$, by counting the integer points over $x=k$ and adding those together (it is counting by columns). Try counting by rows instead. Equivalently, reflect the picture along the line $y=x$. Equivalently, consider the curve $y=x^2$. – NDB Aug 05 '23 at 13:10
  • https://oeis.org/A022554 – Arthur Aug 05 '23 at 13:25
  • 1
    These are two common techniques: (1) If a function is annoying, like $\lfloor\sqrt{x}\rfloor$, sometimes its inverse function is nicer. So, you switch to study that one instead. (2) When you have double summation $\sum _m(\sum _n f(m,n))$, or integration $\int(\int f(x,y)dx)dy$, consider changing the order of summation to see if the reverse order is simpler to compute.

    You only need to note that $\lfloor\sqrt{x}\rfloor=\sum_{k\leq \sqrt{x}}1$ to see your sum as a double summation.

     – NDB Aug 05 '23 at 13:42

0 Answers0