For what $c > 0$ is $S = \lfloor \left( n+1 \right)^c \rfloor - \lfloor n^c \rfloor$ non-decreasing?
For the first bullet, $1.96 \lt x \le 2$, as $S_{7958491,1.96}=8261400,S_{7958492,1.96}=8261399$ and for $c \gt 2$ the difference without the floor signs is $\gt 2$. My program gets slow checking more than $10^7$
Proof outline:
- Define $f(x) = (x+1)^c - x^c$. Obviously $f(n) - 1 \lt S_{n,c} \lt f(n) + 1$. Therefore it is sufficient for $f(x+1) - f(x) \ge 2$ to make sure the sequence is non-descending.
- This means that if $f'(x) \ge 2$ the sequence is definitely non-descending. Which means $f'(x) = c(x+1)^{c-1} - cx^{c-1} \ge 2$.
- For $c=2$ we actually have an equality, but for $c<2$ the derivative tends to 0, meaning $\lim f'(x) = 0$. Therefore at some point $f'(x) < \epsilon$ and $f(x+1) - f(x) < \epsilon$.
- Define $g(n) = S_{n,c}-f(n)$. $f(x)$ tends to infinity, but the derivative tends to $0$. Therefore we may assume that for sufficiently large $n$, $f(x)$ is very nearly constant. In this neighborhood, whenever $g(n) > 0$ but $g(n+1) < 0$ we have a decrease, because $f(n+1) \approx f(n)$. $g(x)$ switches sign infinitely many times, and for all $m$ there exists $n$ such that $g(m+n)$ has a different sign than $g(m)$.
- We go to an $m$, where the sign of $g(m)$ is positive but the sign of $g(m+1)$ is negative, and we have our "winner".
- So the critical value is $c = 2$. For non-integer $c<2$, $S_{n,c}$ won't be strictly non-decreasing, but for values close enough to $2$ we'll have to go farther and farther towards infinity to find the counter-example.
For $c=1$ we have $S_{n,1} = 1$ and therefore non-decreasing. For $c<1$ we have $S_{n,c} = 0$ for sufficiently large $n$, therefore it can't be non-decreasing.
To summarize:
- $ c >= 2$ non-decreasing because of the derivative.
- $ 2 > c > 1 $ is not non-decreasing because of the derivative.
- $ c = 1$ non-decreasing because of the constant value ($1$).
- $ 0 < c < 1$ decreasing because $S_{n,c} = 0$ infinitely many times.
- $ c <= 0$ non-decreasing because of the constant value ($0$).