Recursive formula (IMO 2017 #3) The  2017 International Math Olympiad posed a question involving a rabbit and hunter https://artofproblemsolving.com/community/c6h1480157_imo_2017_problem_3
Assume:


*

*the rabbit always moves 1 unit on a vector away from the hunter

*the tracker always emits a signal which is 1 unit perpendicular to that vector

*the hunter always moves 1 unit on a vector toward the position reported by the tracker


The distance d(n) between hunter and rabbit after n rounds can be expressed recursively as
$$ d(n)  = \sqrt{((d(n-1)+1)^2 +1} -1 $$
Essentially, the problem is asking whether d(1e9) can feasibly be larger than 100.
With the use of computer and spreadsheet tool one can show that
$$ d(n)  = \sqrt{n - 2\sqrt{n+1} +2}  $$
Question: how could one derive the non-recursive expression of d(n) without benefit of a computer spreadsheet

Notice that $(d(n)+1)^2 = (d(n-1)+1)^2+1$ so if you define $f(n) = (d(n)+1)^2$ all you have to do is solve the recursive relation
$$
f(n) = f(n-1)+1.
$$
This isn't too hard to solve, with solution $f(n) = n+1$. So $d(n) = \sqrt{f(n)}-1 = \sqrt{n+1}-1$. This is equal to your solution, just written in a nicer way.
