16
$\begingroup$

Let $\left(\, x_{n}\,\right)_{\,n\ \geq\ 1}$ be a sequence defined as follows: $$ x_{1}={1 \over 2014}\quad\mbox{and}\quad x_{n + 1}=x_{n} + x_{n}^{2}\,, \qquad\forall\ n\ \geq\ 1 $$ Compute the integer part of the sum: $$ S=\frac{x_1}{x_2} + \frac{x_2}{x_3} + \cdots +\frac{x_{2014}}{x_{2015}}\,,\qquad \left(\,\mbox{i. e.}\ \left\lfloor\, S\,\right\rfloor\,\right)$$

Any nice idea to approach this? How can one find a formula for $x_{n}$? Thank you!

$\endgroup$
  • $\begingroup$ Recurrence relations aren't solvable in general. Are you sure that there is a solution? $\endgroup$ – charlotte Dec 11 '14 at 17:23
  • $\begingroup$ It is clearly that not all recurrences have a closed form. This is from a youth magazine. $\endgroup$ – user85046 Dec 11 '14 at 17:27
  • $\begingroup$ Alright, so there should be an answer, thanks. And yes, I meant a closed form solution in terms of $n$. $\endgroup$ – charlotte Dec 11 '14 at 17:29
  • $\begingroup$ You are welcome! Maybe there is a mistske, but I'm interested in solving the problem as it is! At first sight I thought it is easy, but I have never been so wrong. $\endgroup$ – user85046 Dec 11 '14 at 17:40
  • $\begingroup$ Deceptively simple, isn't it? I've taken a few stabs at it, but nothing seems to be working. Unfortunately, I have to get back to studying for my exams. $\endgroup$ – charlotte Dec 11 '14 at 17:42
12
+150
$\begingroup$

To get a bound on $\dfrac{1}{x_{2015}}$, let $y_n = \dfrac{1}{x_n}$. Then, $\dfrac{1}{y_{n+1}} = \dfrac{1}{y_n}+\dfrac{1}{y_n^2} = \dfrac{y_n+1}{y_n^2}$.

Hence, $y_{n+1} = \dfrac{y_n^2}{y_n+1} = y_n-\dfrac{y_n}{y_n+1}$. Rearrange to get $\left(1+\dfrac{1}{y_n}\right)(y_n-y_{n+1}) = 1$.

Since $y_n$ is a decreasing sequence and $1+\dfrac{1}{y}$ is a decreasing function, we have:

$2014 = \displaystyle\sum_{n = 1}^{2014}\left(1+\dfrac{1}{y_n}\right)(y_n-y_{n+1}) = \sum_{n = 1}^{2014}\int_{y_{n+1}}^{y_n}\left(1+\dfrac{1}{y_n}\right)\,dy \le \sum_{n = 1}^{2014}\int_{y_{n+1}}^{y_n}\left(1+\dfrac{1}{y}\right)\,dy = \int_{y_{2015}}^{y_1}\left(1+\dfrac{1}{y}\right)\,dy = \left[y + \ln y\right]_{y_{2015}}^{y_1} = (2014+\ln 2014)-(y_{2015}+\ln y_{2015})$

Therefore, $y_{2015}+\ln y_{2015} \le \ln 2014$. Exponentiation yields $y_{2015}e^{y_{2015}} \le 2014$.

If you can convince yourself that $6e^6 > 2014$, then we have $y_{2015} \le 6$ (because $ye^y$ is increasing).

Therefore, $S = 2014 - y_{2015} \ge 2008$. It remains to show that $S \le 2009$, i.e. $y_{2015} \ge 5$.

$\endgroup$
17
$\begingroup$

Your sum is telescoping since

$$S={\displaystyle \sum_{k=1}^{2014}\frac{x_{k}}{x_{k+1}}=\sum_{k=1}^{2014}\frac{x_{k}^{2}}{x_{k}x_{k+1}}=\sum_{k=1}^{2014}\frac{x_{k+1}-x_{k}}{x_{k}x_{k+1}}=\sum_{k=1}^{2014}(\frac{1}{x_{k}}-\frac{1}{x_{k+1}})} $$ $$ {\displaystyle =\frac{1}{x_{1}}-\frac{1}{x_{2015}}=2014-\frac{1}{x_{2015}}.}$$

Hence it's a matter of evaluating $x_{2015}$. It seems that $.17<x_{2015}<.18$ and $S=2008.22$.

Some identities that might help $$ x_{2015}=x_1+\sum_{k=1}^{2014} x_k^2;\ x_{2015}=x_1(1+x_1)(1+x_2)\cdot\ldots\cdot(1+x_{2014})$$probably with some inequalities involving sums and products.

$\endgroup$
  • $\begingroup$ I knew that the sum is telescoping. My problem is with $x_{2015}$. How do you get that inequality, @Silencer? $\endgroup$ – user85046 Dec 14 '14 at 8:11
  • $\begingroup$ I made mistake. Sorry. $\endgroup$ – Tacet Dec 14 '14 at 10:07
  • $\begingroup$ Look also here. You can take bigger precision, and (if I didn't make mistake) receive the answer should be 2008. $\endgroup$ – Tacet Dec 14 '14 at 10:30
  • 1
    $\begingroup$ @CFG Would you be so kind and edit your problem so that it reflects the things you knew like the fact that the sum is telescoping and that it reduces to $x_{2015}$? $\endgroup$ – Neutral Element Dec 14 '14 at 15:39
  • $\begingroup$ @Silencer If the answer 2008 is correct then it makes the mathematical proof of this problem even more interesting! $\endgroup$ – Neutral Element Dec 14 '14 at 19:12
5
$\begingroup$

JimmyK has ignored the request (in now deleted comments) to add the lower bound proof to his answer, so I will add an answer with the lower bound proof which will resolve the question completely.

Just like Jimmy's excellent upper bound proof we use

$$ 2014 = \sum_{n=1}^{2014}\left(1 + \frac{1}{y_n}\right)(y_n - y_{n+1}) = \sum_{n=1}^{2014} \int_{y_{n+1}}^{y_n} \left(1 + \frac{1}{y_n}\right) dy$$

Now we can easily show by induction that $y_k \gt -1$ and thus

$$y_{n+1} + 1 \gt y_{n+1} + \frac{y_n}{1+y_n} = y_n$$

Thus we have that

$$\left(1 + \frac{1}{y_n}\right) \ge \left(1 + \frac{1}{y_{n+1} +1}\right)$$

Now for $-1 \lt y_{n+1} \le y$ we have that

$$\left(1 + \frac{1}{y_{n+1} +1}\right) \ge \left(1 + \frac{1}{y +1}\right)$$

Thus $$\left(1 + \frac{1}{y_n}\right) \ge \left(1 + \frac{1}{y +1}\right)$$

Let $a = y_{2015}$

We thus have

$$ 2014 = \sum_{n=1}^{2014} \int_{y_{n+1}}^{y_n} \left(1 + \frac{1}{y_n}\right)dy \ge \sum_{n=1}^{2014} \int_{y_{n+1}}^{y_n} \left(1 + \frac{1}{y +1}\right) dy = \int_{a}^{2014} \left(1 + \frac{1}{y +1}\right) dy =$$ $$ 2014-a + \log(2015) - \log(a+1)$$

Thus

$$ 2014 \ge 2014-a + \log(2015) - \log(a+1)$$

which means

$$ a + \log(a+1) \ge \log (2015)$$

giving us

$$ (a+1)e^{a} \ge 2015$$

Now $6e^5 \lt 6 \times3^5 = 1458$ and since $(x+1)e^x$ is increasing, we have $$a \gt 5$$

This coupled with the other two answers gives the answer of $$2008$$


An observation:

$$y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)}$$

where $f(y) = ye^y$.

This is a Newton Raphson recurrence and techniques used there should be applicable here.

$\endgroup$
  • 2
    $\begingroup$ @CFG: You are welcome. Can you please tell us the name of the youth magazine? Sounds like a very interesting one... $\endgroup$ – Aryabhata Dec 19 '14 at 19:34
  • $\begingroup$ @CFG: Thanks...! $\endgroup$ – Aryabhata Dec 23 '14 at 17:44
  • $\begingroup$ Interesting. CFG deleted his comment. The magazine is apparently Gazetta Mathematica. I was unable to find it in there though (didn't look too hard). $\endgroup$ – Aryabhata Jan 9 '15 at 3:21
  • $\begingroup$ Please delete your comment. It's from an additional collection of this magazine (for fun), which can't be found on the internet. $\endgroup$ – user85046 Jan 10 '15 at 8:52
  • 1
    $\begingroup$ @CFG: I don't understand. What is wrong with mentioning the source? Someone who has physical access can take a look. $\endgroup$ – Aryabhata Jan 10 '15 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy