# How do you solve this recurrence relation/use it in a sequence to find it's GIF value?

The sequence {$x_k$} is defined by $x_{k+1} = x_k^2 + x_k$ and $x_1=\frac{1}{2}$. Now, if [.] denotes the greatest integer function, then which of the following options is correct:

A) $[\frac{1}{x_1 + 1} + \frac{1}{x_2 + 1} + ... + \frac{1}{x_{100} + 1}] = 1$

B) $[\frac{1}{x_1 + 1} + \frac{1}{x_2 + 1} + ... + \frac{1}{x_{101} + 1}] = 1$

C) Both the options

D) None of the options

I have no idea how to go about solving this sum. I tried replacing $\frac{1}{x_k + 1}$ by $\frac{x_k}{x_{k+1}}$, but didn't get anywhere. I also tried writing each term as $$\frac{1}{{(x_{k} + 1)}^2-x_k}$$

and then tried to convert it to a telescoping form, but didn't get anywhere.

Any help will be appreciated.

• How did you get $\frac{1}{\left(x_{k+1}+1\right)^2-x_k}$? Dec 11 '15 at 18:26
• @user236182 Sorry, corrected it. After correction, it becomes evident that it can't be converted to telescoping in that form. My bad. Dec 11 '15 at 18:29

I found that you don't need to solve the sequence to answer the question. $$x_{k+1} = x_k^2 + x_k=x_k(x_k+1)$$ $$\frac1{x_{k+1}} =\frac1{x_k(x_k+1)}=\frac1{x_k}-\frac1{x_k+1}$$ $$\frac1{x_k+1}=\frac1{x_{k}}-\frac1{x_{k+1}}$$ $$\sum_{k=1}^{100} \frac1{x_k+1}=\sum_{k=1}^{100}\left(\frac1{x_{k}}-\frac1{x_{k+1}}\right)=\frac1{x_{1}}-\frac1{x_{101}}=2-\frac1{x_{101}}$$ $$x_3>1 \rightarrow \frac1{x_{102}}<\frac1{x_{101}}<\frac1{x_3}<1$$ $$\therefore \lfloor \sum_{k=1}^{100}\frac1{x_k+1}\rfloor=\lfloor \sum_{k=1}^{101}\frac1{x_k+1}\rfloor=1$$ Therefore the answer is "C) Both of the options".