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.