Since $a_{n+1} \,=\, a_n + a_n^{-1}$ for $n \ge 1$ , we see that $a_{n+1}^2 - a_n^2 \,=\, 2 + a_n^{-2}$ for all $n \ge 1$ , so that $a_n^2 - 1 \; = \; a_n^2 - a_1^2 \; = \; \sum_{j=1}^{n-1}\big(2 + a_j^{-2}\big)$ for all $n \ge 2$ , and hence $a_n^2 \; = \; 2n-1 + \sum_{j=1}^{n-1}a_j^{-2} \;\ge \; 2n$ for all $n \ge 2$ . Thus we deduce that $2n \; \le \; a_n^2 \; \le \; 2n-1 + \tfrac12 + \sum_{j=1}^{n-1}(2j)^{-1} \; =\; 2n-\tfrac12 + \tfrac12\sum_{j=1}^{n-1}j^{-1}$ for all $n \ge 2$ . Using the standard inequality that $\sum_{j=1}^n j^{-1} \; \le \; \ln n + 1 \qquad n \ge 1\;,$ we deduce that $2n \;\le\; a_n^2 \;\le\; 2n-\tfrac12 + \tfrac12(\ln (n-1) + 1) \; = \; 2n + \tfrac12\ln (n-1)$ for all $n \ge 2$ . This implies that $200000 \; \le \; a_{100000}^2 \; \le \; 200000 + \tfrac12\ln 99999 \; = \; 200005.76$ and hence $447.21 \; \le \; a_{100000} \; \le \; 447.22$ so that $\big\lfloor a_{100000} \big\rfloor \,=\, 447$ .

It is clear from the recurrence relation that the sequence diverges. While $a_n$ may diverge to infinity slowly, $a_n^2$ will diverge to infinity more rapidly, and therefore we might hope to obtain a bound on the size of $\sum_j a_j^{-2}$ . This turned out to be the case.

Disclaimer: This solution is NOT rigorous. Note: When I refer to terms, I am referring to the floor of them, since our desired number is the floor of a certain term.

So whenever I see a problem like this, my favorite approach is always to start with small cases and list out several of the first terms. So here's a list of the FLOOR of the first 30 terms, starting with $a_1: 1,2,2,2,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7$

Now, you may wonder where I get this from, but trust me, it is easier to see when you've written the term number next to each term in the list: The terms increase by 1 at the midpoints of consecutive triangular numbers. Specifically, if we have two consecutive triangular numbers $a, b$ , an increase will occur at the $\left\lceil\dfrac{a+b}{2}\right\rceil^{\text{th}}$ term (where $\lceil n \rceil$ denotes the smallest $m\ge n$ ). At this point I can't exactly prove this, but we can check our list of terms: $a_2 = 2, 2 = \left\lceil\dfrac{3+1}{2}\right\rceil$ $a_5 = 3, 5 = \left\lceil\dfrac{3+6}{2}\right\rceil$ $a_8 = 4, 8 = \left\lceil\dfrac{6+10}{2}\right\rceil$ $a_{13} = 5, 13 = \left\lceil\dfrac{10+15}{2}\right\rceil$ $a_{18} = 6, 18 = \left\lceil\dfrac{15+21}{2}\right\rceil$ All of them satisfy our conjecture. Also, note that each of the terms above are the FIRST terms that equal their respective amount (i.e. $a_{18}$ is the FIRST term that is equal to $6$ .

Now, all we have to do is find a triangular number, which is in the form $\dfrac{n(n+1)}{2}$ , near $100000$ . $\dfrac{n(n+1)}{2} = 100000 \implies n^2+n-200000 = 0 \implies n \approx 446.7$ Since $447.5 > 446.7 > 446.5$ , we are past the midpoint of the two triangular numbers nearest $100000$ , so our answer is $\boxed{447}$ by the aforementioned conjecture.

We can create a function $y$ whose Euler's method approximation is $a_n$ . Shifting the indices down $1$ , we have $a_0=1$ and we wish to find $\lfloor {a_{99999}}\rfloor$ . Using a step size of $\frac{1}{99999}$ , $a_{99999}$ will approximate $y(1)$ . We have $y\left(\frac{n+1}{99999}\right) \approx y\left(\frac{n}{99999}\right)+\frac{1}{99999}y'\left(\frac{n}{99999}\right).$ Letting $y'=\frac{99999}{y}$ will give us $y\left(\frac{n+1}{99999}\right) \approx y\left(\frac{n}{99999}\right)+\frac{1}{99999}\cdot\frac{99999}{y\left(\frac{n}{99999}\right)}.$ This will make $a_n$ a good approximation to $y\left(\frac{n}{99999}\right)$ . Solving this differential equation gives $y=\sqrt{199998x+C}$ and using $y(0)=1$ yields $y=\sqrt{199998x+1}$ . Finally, plugging in $1$ for $x$ , $a_{99999}\approx \sqrt{199999}$ and $\lfloor\sqrt{199999}\rfloor=\boxed{447}$ .

Note that $a_2=2$ and $a_{n+1}^2=a_n^2+\frac{1}{a_n^2}+2$ .

Now we have $a_{100000}^2=[\displaystyle \sum_{i=2}^{99999} a_{i+1}^2-a_i^2]+a_2^2$

$=[\displaystyle \sum_{i=2}^{99999} \frac{1}{a_i^2}+2]+1=\displaystyle \sum_{i=2}^{99999} \frac{1}{a_i^2} + 200000$

To create a telescoping series, we note that $\displaystyle \sum_{i=2}^{99999} \frac{1}{a_i\times a_{i+1}}< \displaystyle \sum_{i=2}^{99999} \frac{1}{a_i^2}<\displaystyle \sum_{i=2}^{99999} \frac{1}{a_i\times a_{i-1}}$

$\rightarrow 0<\frac{1}{a_2}-\frac{1}{a_{100000}} < \displaystyle \sum_{i=2}^{99999} \frac{1}{a_i\times a_{i-1}} < \frac{1}{a_1}-\frac{1}{a_{99999}}<1$

Hence $200000<a_{100000}^2<200001$ or $\lfloor a_{100000} \rfloor = 447$ .

Motivation: first I noticed that the question asks for an estimate of $a_{100000}$ , not an exact value, so I wanted to make a number appear in the equation. Squaring the RHS of the equation creates 2, which is what I wanted. Then I guess that the method of differences must appear somewhere as it is the easiest way to create the term $a_{100000}$ . I then realized that I can do this telescoping trick with the sequence $(\frac{1}{a_i^2})$ in order to get a pretty accurate estimate. That's how I figured out the solution.

an+1 ^2 =an^2+1/an^2 +2 an= a1+1/a1+1/a2+….1/an-1 an^2=a1^2+1/a2^2+…..1/an-1^2 +2*n

a100001^2 =a1 ^2+1/a1^2…..1/a100000^2 +200000=(a1 +1/a1 +1/a2+……1/a100000)^2 =>a1 ^2+1/a1^2…..1/a100000^2 +200000= a1^ 2+1/a1^2…..1/a100000^2 +2(a1/a2+a1/a3……….1/a99999a100000) =>100000 = a1(a1+1/a1+1/a2+….1/a100000 –a1) + 1/a1(a1+1/a1+1/a2+….1/a100000 –a1-1/a1)..........a100000(a1+1/a1+1/a2+….1/a100000 - a1-1/a1-1/a2-….1/a100000) a1(a100000-a1) +1/a1(a100000-a1) + 1/a2(a100000 –a2)........1/a100000(a100000-a100000) =>100000=a100000(a100001) -100000 =>200000 = a100000(a100000+1/a100000) =>200000 = a100000^2 +1 =>[√199999] =447

Not a strict one. If we can estimate the upper bound as $a(n)\le f(n)$ , we can accordingly estimate the lower bound as $1+\sum_{k=1}^{n-1}\frac{1}{f(k)}$ . So a tight bound (or the order of divergence) satisfies

$f(n) \sim 1+\sum_{k=1}^{n-1}\frac{1}{f(k)} \approx \sum_{k=1}^{n-1}\frac{1}{f(k)} \approx \int_0^x\frac{dt}{f(t)}$

If you remember $(\sqrt{x})'=\frac{1}{2\sqrt{x}}$ , $f(n)=\sqrt{2n}$ will be a reasonable guess. So just try 446 or 447, given that $\sqrt{200000}\approx 446.891$

We can use this easy C++ code ---

include <constream.h>

void main()

{ clrscr();

long int sum,n=1;

float p=1, q =1,a=0;

while(n<=100000)

{ a=p+q;

p=a;

q= 1/a;

n++;

}

sum=a;

cout<<"\n\n\tSum: "<<sum;

getch();

return;

}

Output: Sum: 447 (Ans)

To solve using pen and paper: based on numerical evidence, I observed that (a_n) is approximately (2n+0.25)^(1/2). Thus, if this claim is true, we just need to plug in n=10^5 to solve the problem. However this is merely a conjecture. I would be grateful if anyone could prove or disprove my claim?

So here's the thing! Now as someone who really likes his short-cuts, I decided to use the programming method to solve the question. Programming really shortens the time taken to solve the problem. The following is the very short lines of code that I used to solve the problem. The code is in Java and I use the NetBeans IDE!

    double[] brilliant_series = new double[100000];

    brilliant_series[0] = 1;

    for(int i = 1 ; i < brilliant_series.length ; i++)
    {
        brilliant_series[i] = brilliant_series[i-1] + (1/brilliant_series[i-1]);
    }
    System.out.println(brilliant_series[99999]);

And the output-- 447.21972185666755 As we're asked for the greatest integer lesser than or equal to the above, the answer is 447!

Cheers!