Denote $n_i=n_{i-1}-\sqrt[k]{n_{i-1}}$. If $n_0=n$ then what is the minimum $i$ at which $n_i<2$ holds? Is there a standard technique to solve such problems? Any references?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
I always like to answer these questions by approximating the difference equation with a differential equation (for which the result is always easier). In this case, the d.e. is $\dot x=-x^{1/k}$, $x(0)=n$, giving $t\approx \frac{k}{k-1}n^{(k-1)/k}$.
answered May 1, 2018 at 16:20
-
$\begingroup$ I first discovered this method as an undergrad, when someone asked me the question "at what rate does $x_n$ approach 0 if $x_0=\frac 12$ and $x_{n+1}=x_n-x_n^2$?" I obtained upper and lower estimates that I was quite delighted with, but it turned out that the only thing the person cared about was the much simpler fact that $x_n\to 0$(!) Ever since then, I periodically find occasion to wheel out my method. $\endgroup$ Commented May 1, 2018 at 17:44
-
$\begingroup$ If someone asked at what rate $x_n$ approaches 0, how could the person have only cared about whether $x_n$ approaches 0? $\endgroup$– KConradCommented May 1, 2018 at 19:09
-
2$\begingroup$ My thoughts exactly. It is possible that I incorrectly perceived they were asking about the rate. Also don't forget we were young and naive. $\endgroup$ Commented May 1, 2018 at 19:26
-
$\begingroup$ This is a nice heuristic, but how can we use it to actually prove something about the original recurrence? Can we get bounds for the desired $i$, for example? $\endgroup$ Commented May 1, 2018 at 19:33
-
2$\begingroup$ @NateEldredge: So you obtain an upper bound on $i$ using this differential equation (the difference equation moves at speed $−x_0^{1/k}$ for time 1,then speed $−x_1^{1/k}$ for time 1 etc, whereas the differential equation immediately slows down, so that the solution to the difference equation is strictly smaller at integer times than the solution to the differential equation). If you want a differential equation that moves faster than the difference equation you can solve $\dot x=−(F(x))^{1/k}$, where $F(x)$ is the inverse function of $x\mapsto x−x^{1/k}$. $\endgroup$ Commented May 1, 2018 at 22:22