3
$\begingroup$

Maybe it's a simple question... Fix a positive $N$. Let $a_{n}$ be the recursive sequence:

$$a_{1} = N$$ $$a_{n}=a_{n-1}-(a_{n-1})^{\frac{2}{3}}.$$

How many steps do I have to complete in order to have $a_{n}\leq 1$? And, more general, changing $\frac{2}{3}$ by $\frac{2+\varepsilon}{3}$...

The problem here is that I'm not trying to find the limit, but the moment where I achieve the quantity 1.

This question is related to the more general one:

Given a recurrence equation, are there techniques for estimating asymptotics of the solution?

And, too, in graph theory, there are processes where $N$ is the number of edges and the steps here would be the amount of components of your graph. Basically, the techniques that could answer these recursive questions would help on graph's counting problem.

Do you have any hints? Thanks a lot

Improve this question
$\endgroup$
5
  • $\begingroup$ The way I like to approach questions like this (not unlike one of the answers in the post in Serguei Popov's answer) is to approximate the difference equation by the differential equation $\dot x=-x^{2/3}$. For this d.e., it's easy to answer your question. $\endgroup$
    – Anthony Quas
    Commented Oct 31, 2016 at 15:27
  • 3
    $\begingroup$ I don't see why this question was closed. I think it's a perfectly reasonable question for this site. Basically "Given a recurrence equation, what are some techniques for estimating asymptotics of the solution?" I think this is more of a research question than a general mathematics question. $\endgroup$
    – Anthony Quas
    Commented Oct 31, 2016 at 22:29
  • $\begingroup$ Your question was put on hold, the message above (and possibly comments) should give an explanation why. If you have some ideas how to improve the post, the next edit should put it into reopen review queue, where users can vote whether to reopen it or leave it closed. (In fact, it went in the queue at least once already, probably based on somebody casting a reopen vote.) $\endgroup$
    – Martin Sleziak
    Commented Nov 1, 2016 at 8:16
  • $\begingroup$ Dear Professor @AnthonyQuas, as I'm not so familiar with the kind of question I asked, I couldn't see how your differential equation's approach would answer it, for the sequence case. Could you explain this point, please? Thanks for your attention. $\endgroup$
    – Bruno Brogni Uggioni
    Commented Nov 3, 2016 at 15:43
  • 1
    $\begingroup$ The idea is that if you solve the differential equation $\dot x=-x^{2/3}$, then in one time step, $x$ changes by approximately $-x^{2/3}$ (not exactly because the differential equation slows down, but this is a good approximation). That means that $x(t+1)\approx x(t)-x(t)^{2/3}$. This is the same thing as the difference equation. $\endgroup$
    – Anthony Quas
    Commented Nov 3, 2016 at 16:18

1 Answer 1

Reset to default
2
$\begingroup$

You may find it useful to look here: http://www.artofproblemsolving.com/community/c7h398470 (in particular, the link in the 1st post, and also fedja's answer).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .