1

Let $a(n)$ be a sequence with $a(0)=1/2$ and $a(n+1)=a(n)+(a(n)^2)/2013$, $n$ natural number.

Determine the least natural number $k$ such that $a(k)>1$. This problem is from Poland proposed to Romanian Masters of Mathematics. Can you give me some hints? I don't want a complete solution. Thank you!

Daniel Robert-Nicoud
  • 29,795

2 Answers2

3

Motto: To iterate a quadratic function is basically impossible, to iterate a homographic function is trivial.

Consider any sequence $(x_n)$ defined by $x_{n+1}=x_n+\frac1cx_n^2$ for some $0\lt x_0\lt 1\lt c$. Then, for every $0\lt x\lt 1$, $$ \frac{c+1}{c+1-x}\lt1+\frac{x}c\lt\frac{c}{c-x}, $$ hence, as long as $x_n\lt 1$, $$ \frac{c+1}{c+1-x_n}x_n\lt x_{n+1}\lt\frac{c}{c-x_n}x_n, $$ that is, $$ \frac1{x_n}-\frac1c\lt \frac1{x_{n+1}}\lt\frac1{x_n}-\frac1{c+1}. $$ Thus, $$ \frac1{x_0}-\frac{n}c\lt\frac1{x_n}\lt\frac1{x_0}-\frac{n}{c+1}, $$ for every $n$ such that $$ \frac1{x_0}-\frac{n-1}c\geqslant1, $$ that is, such that $n\leqslant(c/x_0)-c+1$. Assume that $c$ is an integer and that $x_0\leqslant1/2$. Then $n=c$ and $n=c+1$ are admissible. For $n=c$, the lower bound of $1/x_n$ is $1/x_0-1$. For $n=c+1$ the upper bound is $1/x_0-1$, hence $$ \frac1{x_{c+1}}\lt\frac1{x_0}-1\lt\frac1{x_c}. $$

For every integer $c\geqslant2$ and $x_0\leqslant1/2$, the least $n$ such that $x_n\gt x_0/(1-x_0)$ is $n=c+1$. In particular, if $x_0=1/2$, the least $n$ such that $x_n\gt1$ is $n=c+1$.

Did
  • 279,727
  • How, after "thus" ? –  Oct 06 '13 at 08:41
  • @CFG Iterating the line immediately before. – Did Oct 06 '13 at 09:14
  • I'm sorry if I insist about this, but could you please explain hwo you iterate that line? –  Oct 07 '13 at 12:40
  • Let $y_n=1/x_n$ and $a=1/(c+1)$. You know that $y_{n+1}\lt y_n-a$ for every $n\geqslant0$ and you wish to show that $y_n\lt y_0-na$ for every $n\geqslant0$, right? – Did Oct 07 '13 at 13:17
  • Yes...I didn't understand how to come to that n/(c+1). –  Oct 07 '13 at 13:29
  • Well, i didn't have so much time, but today I looked up after this solution. There might be some problems...During the proof, you said x(n)<1. So, then how is the last afirmation regarding x(n)>1? Another thing...For x(0)=1/4 is 1/x(c+1)<3 and follows what? You said n<=c/x(0) - c +1 and 1/x(0) - (n-c)/c<1 and they are opposite. –  Oct 10 '13 at 18:44
  • The proof determines the indexes n such that x(n)<1 and the first index n such that x(n)>1. Where is the problem? // Yes, for x(0)=1/4, 1/x(c+1)<3<1/x(c) hence the first index n such that x(n)>1/3 is n=c+1. Where is the problem? // About the inequality involving 1/x(0)-(n-c)/c, indeed the inequality sign was reversed, thanks for mentioning it. – Did Oct 10 '13 at 21:14
  • Hello! I just saw your response now. Regarding x(n)<1...You use it during the proof and you just can't say that x(n)>1 at the end because the whole proof was based on x(n)<1. That's what I think. Maybe we can write it somehow to make this proof correctly –  Nov 03 '13 at 10:54
  • Here is a suggestion: try to read carefully a proof before asserting it is flawed. In the present case, the proof works, trivially (and I am a little tired of reading assertions of the contrary). If ever you take the time to READ before slandering, you will see that the proof gives information on x(n+1) as long as x(n)<1 hence the bounds on x(c+1) are valid (even though x(c+1)>1) since x(c)<1. – Did Nov 03 '13 at 11:51
0

I was working out the details when Did posted basically the same solution that I had in mind, so I won't repeat it here. But I thought I could say a thing or two about how one can come to a solution like this. At least that is how I came to it.

Our sequence is given by relation $a_{n+1} - a_n = a_n^2 / c$. Notice that $a_n^2/c$ is very small in our case, so we have a kind of a discrete system that moves step by step, making very small steps.

We could try to approximate it by looking at its continuous version, given by the differential equation $$ f'(t) = f^2(t) / c. $$ and the boundary condition $f(0) = a(0)$.

The equation can be rewritten as $df/f^2 = dt/c$, and the solution then is: $$ \frac{1}{a(0)} - \frac{1}{f(t)} = \frac{t}{c}. $$

So it is logical to expect that $\frac{1}{a(0)} - \frac{1}{a(n)}$ is somewhere around $\frac{n}{c}$. Then one can try and prove the inequalities as in Did's answer.

Dan Shved
  • 15,862
  • 39
  • 55