4
$\begingroup$

There is a recurrence sequence $x_1 = \frac{1}{2}$, $x_{n+1} = x_n^2 + x_n$. How much is floor of $\frac{1}{x_1 + 1} + \frac{1}{x_2 + 1} + ... + \frac{1}{x_{100} + 1}$? Floor is an integer part of a real number.

$\endgroup$

closed as off-topic by Carl Mummert, Parcly Taxel, JonMark Perry, TheSimpliFire, man and laptop Feb 4 '18 at 13:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Carl Mummert, Parcly Taxel, JonMark Perry, TheSimpliFire, man and laptop
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ Hint: $\frac{1}{x_{n+1}} = \frac{1}{x_n} - \frac{1}{x_n+1}$ and $x_3 > 1$. $\endgroup$ – achille hui Feb 2 '18 at 11:02
2
$\begingroup$

The instructive hints of @AchilleHui deserve an answer by its own.

Given the recurrence relation \begin{align*} x_{n+1}&=x_n(x_n+1)\tag{1}\\ x_1&=\frac{1}{2}\\ \end{align*}

we derive from (1) a telescoping representation of the reciprocal values via \begin{align*} \frac{1}{x_{n+1}}&=\frac{1}{x_n(x_n+1)} =\frac{1}{x_n}-\frac{1}{x_n+1} \end{align*}

We obtain \begin{align*} \sum_{j=1}^{100}\frac{1}{x_j+1}&=\sum_{j=1}^{100}\left(\frac{1}{x_j}-\frac{1}{x_{j+1}}\right)\\ &=\sum_{j=1}^{100}\frac{1}{x_j}-\sum_{j=2}^{101}\frac{1}{x_j}\tag{2}\\ &=\frac{1}{x_1}-\frac{1}{x_{101}}\\ &=2-\frac{1}{x_{101}}\tag{2} \end{align*}

From $x_1=\frac{1}{2}$ and (1) we get $x_2=\frac{3}{4}, x_3=\frac{21}{16}>1$ and it follows again from (1) $x_n>1$ with $n\geq 3$.

We finally get from (2) \begin{align*} \color{blue}{\left\lfloor 2-\frac{1}{x_{101}} \right\rfloor = 1} \end{align*}

Note: Since $x_1=\frac{1}{2}$ and $x_{n+1}\approx x_n^2$ we have $x_{101}\approx \frac{1}{2^{2^{100}}}$. So, the difference of $2-\frac{1}{x_{101}}$ to the value $2$ is very small.

$\endgroup$
  • $\begingroup$ For all practical purposes, this sums to 2, but since it is less than 2 by some finite (though unimaginably small) amount, the floor is 1. $\endgroup$ – AlexanderJ93 Feb 3 '18 at 20:42
  • 1
    $\begingroup$ @AlexanderJ93: Thanks for the credit. That's why I've added the note. We have to carefully consider precision settings when doing numerical calculations. This is a good example showing that $\pm 1$ errors might occur relatively easy. This could lead to problematic situations when used in critical code sections. $\endgroup$ – Markus Scheuer Feb 3 '18 at 20:54
  • $\begingroup$ I see. I think what confused me was saying that the difference is small, when in fact the difference is nearly 2. $\endgroup$ – AlexanderJ93 Feb 3 '18 at 20:55
  • 1
    $\begingroup$ @AlexanderJ93: Thanks, wording corrected. $\endgroup$ – Markus Scheuer Feb 3 '18 at 20:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.