KenZuuuu's blog

By KenZuuuu, history, 6 months ago, In English

Hi everyone,

I’ve been dealing with some sequence problems where I need to check if the sequence is increasing or decreasing. Usually, I just look at u_{n+1} — u_n, but for some complex functions, it gets messy.

I’ve been trying to use the derivative f'(x) (treating n as x) to check for monotonicity. It makes things much easier, but I’m a bit worried about the domain. Since f'(x) is for x ∈ R and a sequence is only defined for n ∈ N*, is this approach always rigorous? Or are there cases where this might fail?

For instance, if I have u_n = 2^n — an, what’s the best way to find the range of a so that the sequence is strictly increasing? Should I stick to the derivative or is there a better "competitive programming" way to handle this?

Any advice would be great. Thanks!

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
6 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like it

If $$$f(x)$$$ is monotonic then so is $$$u_n$$$. But the inverse is not necessarily true

See $$$u_n=\frac{\cos(2\pi n)}{n}$$$.

  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    tks you!!!!! and could you suggest any alternative methods for determining the monotonicity (increasing or decreasing nature) of a sequence when calculating the difference proves too difficult?

    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      you could compute the ratio $$$\frac{a_n}{a_{n+1}}$$$ and compare it with 1.

      • »
        »
        »
        »
        6 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        this only works if (an) is nonzero after a certain rank and if (an) has a fixed sign after a certain rank otherwise its wrong take the alternating sequence (-1)^n it s not monotonic but using this argument it s gives the ration less than 1 always

»
6 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Yes, this method can be used if computing derivatives is easier than computing differences. You're just extending a function from integers to reals, if its derivative has the same sign everywhere in a real interval (not just at integer values), it'll be monotonous on that interval whether in reals or integers.

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

its not necessarily true since the derivative is the change at that point (n) for the analytic continuation, but u care about the change over an interval of length 1, so it might be decreasing at that point but u may see an overall increase, like for example: cos(2pin)exp(n) if the derivative does not change sign yea ig then u can, u can also try breaking the sequence to see if it is increasing, like for n^2/(n^2+1) u can see at 0 it is 0, it has a finite limit and since numerator and denominator grow at the same rate is most probably is monotonically inc, which it is.

  • »
    »
    6 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Could you suggest any alternative methods for determining the monotonicity (increasing or decreasing nature) of a sequence when calculating the difference proves too difficult?

    • »
      »
      »
      6 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      look up ratio test, if an+!/an > 1 its inc, also, u can use the fact R is an ordered field, so an^3,logan,e^an all are inc if an is and vice versa

»
6 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

In competitive programming, a better way to check monotonicity of something is with induction, i.e. you might find something like this:

If it's possible to construct an array with score $$$k$$$, it is also possible to construct an array with score $$$k - 1$$$ for $$$k \gt 0$$$

But for more math oriented problems it works, other than the case where $$$f(x)$$$ is not monotonic and $$$u_x$$$ is as others stated

»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i think that derivative method works but can be overly strict -- for $$$u_n = 2^n - an$$$, just compute $$$u_{n+1} - u_n = 2^n - a \gt 0$$$, and since $$$2^n$$$ is minimized at $$$n=1$$$, you get $$$a \lt 2$$$. using $$$f'(x)$$$ would give $$$a \lt 2\ln 2 \approx 1.386$$$, which is a tighter (and wrong) bound, so stick to the direct difference when hunting exact parameter ranges.