9
$\begingroup$

I recently solved a practical sequence problem, but got curious and tried to generalize it. Let

$$ S_{n, c} = \lfloor \left( n+1 \right)^c \rfloor - \lfloor n^c \rfloor $$

be a set of sequences where $ n \in \mathbb{N}, c \in \mathbb{R}^+ $, that is the positive reals. I'm not sure if my notation is clear, but as an example, $ S_{5, 1.1} $ represents the 5th term in the sequence where $ c = 1.1 $. Since $ S_{5, 1.1} = 2 $ and $ S_{6, 1.1} = 1 $, this is an example of a decreasing sequence.

For what values of $c$, then, is the sequence non-decreasing?

Using the binomial theorem, I was able to prove that it's non-decreasing when $ c $ is an integer, but I've so far not been able to extend that. Any help is greatly appreciated!


Edit: My original question asked just for the following two specific cases, which are still the most interesting cases for me, and would still be helpful if a general solution cannot be obtained:

  • What is the smallest $ x \in \mathbb{R}^+ $ such that for all sequences $ S_{n, c} $ where $c \ge x, S_{n, c} $ is non-decreasing (if it exists)?
  • What is the smallest $ c \ne 1 $ for which it is non-decreasing?
$\endgroup$
3
+100
$\begingroup$

Proof outline:

  1. 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.
  2. 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$.
  3. 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$.
  4. 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)$.
  5. 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".
  6. 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.
  7. 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.

  8. 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$).
$\endgroup$
  • $\begingroup$ I'm having trouble understanding point 4. How is $g(x)$ guaranteed to switch signs infinitely many times, especially given that $c = 1$ is a valid non-decreasing sequence? $\endgroup$ – DPenner1 Feb 22 '16 at 19:22
  • 1
    $\begingroup$ When c = 1 the sign is actually neither positive or negative, because g(x) = 0 always. The thing is, when c is not integer the sign is bound to change because at some point (n+1)^c mod 1 will be smaller than n^c mod 1. And at some point n^c mod 1 will be smaller than (n+1)^c mod 1. $\endgroup$ – Alon Navon Feb 22 '16 at 19:32
  • 1
    $\begingroup$ (n+1)^c - n^c grows ever so slowly when c < 2 and n tends to infinity. So on the one hand at some point (n+1)^c - n^c grows by less than 0.00001 each step, but on the other hand (n+1)^c - n^c diverges, so we know that all those little steps must accumulate past 1 at some point. So there definitely are sign flips. $\endgroup$ – Alon Navon Feb 22 '16 at 19:37
  • 1
    $\begingroup$ For $0<c<1$ don't you mean that $S_{n,c}$ is infinitely often zero? $\endgroup$ – Erick Wong Feb 22 '16 at 23:59
  • 1
    $\begingroup$ I clarified the statement anyway. But yes, a single index suffices. $\endgroup$ – Alon Navon Feb 23 '16 at 0:02
3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks for the tighter bounds. It's starting to look like $ x = 2 $, but that's just a conjecture. $\endgroup$ – DPenner1 Mar 27 '13 at 0:35
  • $\begingroup$ @DPenner: For what it is worth, nothing found at $n=1.965$ under $50,000,000$ $\endgroup$ – Ross Millikan Mar 27 '13 at 0:46

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.