Given $N$ find the number of natural numbers less than $N$ that may be written in the form $\frac{(k)(k+1)}{2}$

Question

Given $N$, find the number of natural numbers less than $N$ that may be written in the form $$\frac{k(k+1)}{2},$$ where $k\in \Bbb N$.

I know that the answer to this problem is approximately $\sqrt {2N}$, but I have no idea how to prove this.

Answer 1

(NOTE: I am counting $0$ as a natural number, so $0$ is one of the solutions since $0=\frac{0(0+1)}{2}$.)

We have the following inequality: $$\frac{k(k+1)}{2} < N$$

We need to solve for $k$ in terms of $N$. Multiply both sides by $2$ and distribute the $k$ on the left side: $$k^2+k < 2N$$

Subtract both sides by $2N$: $$k^2+k-2N < 0$$

Quadratics with positive coefficients are negative in between the zeroes of the polynomial, so we can use the quadratic formula to find the range of possible $k$: $$\frac{-1-\sqrt{1^2-4\cdot 1\cdot -2N}}{2\cdot 1} < k < \frac{-1+\sqrt{1^2-4\cdot 1\cdot -2N}}{2\cdot 1}$$

First, before we simplify this, notice that $0$ satisfies the original inequality. Therefore, the minimum is less than $0$. However, we only care about natural numbers, so we know that $k > 0$. Therefore, we can get rid of the minimum: $$k < \frac{-1+\sqrt{1^2-4\cdot 1\cdot -2N}}{2\cdot 1}$$

Now, simplify: $$k < \frac{-1+\sqrt{1+8N}}{2}$$ $$k < -\frac 1 2+\sqrt{\frac 1 4+2N}$$

Now, depending on what $N$ is, this could be $\lfloor \sqrt{2N} \rfloor-1$ or $\lfloor \sqrt{2N} \rfloor$ solutions, but the answer is $\approx \sqrt{2N}$ solutions.