Making a conjecture of a closed form

Question

There's a formula given $$ T(m,n) = \left\{ \begin{array}{l l} 1 & \quad \text{if $m=0$}\\ 1+T(n \mod m, m) & \quad \text{if $m>0$} \end{array} \right.$$ We're told to use repeated substitution to make a conjecture about a closed form for $T(F(n),F(n+1))$, where $F(k)$ is the $k^{th}$ Fibonacci number.This is a practice question and I have no idea how to start. Could someone help?

Answer 1

For $F_0 = 0, F_1 = F_2=1, \dotsc$ consider

$$ \begin{align} T(F_n, F_{n+1}) &= 1+T(F_{n+1}\mod{F_n}, F_n) & \text{by definition}\\ &= 1+T(F_{n-1}\mod{F_n}, F_n) & \text{since }F_{n+1} = F_n+F_{n-1}\\ &= 1+T(F_{n-1}, F_n) & \text{since }F_{n-1} \le F_n\\ \end{align} $$ continuing, we see $$ \begin{align} T(F_n, F_{n+1}) &= 1+T(F_{n-1}, F_n)\\ & = 2 +T(F_{n-2}, F_{n-1})\\ & = 3 +T(F_{n-3}, F_{n-2}) \end{align} $$ and in general $$ T(F_n, F_{n+1}) = k+T(F_{n-k}, F_{n-k+1}) $$ so when $k=n$ we have $$ T(F_n, F_{n+1}) = n+T(F_0, F_1) = n+T(0, 1) = n+1 $$ Now to make a conjecture about the growth of $T(F_n, F_{n+1})$ we need to find how large $n+1$, the run time, will be in terms of the size of $F_{n+1}$. There is a closed form for this, namely $$ F_k = \frac{\phi^k-\psi^k}{\sqrt{5}} $$ where $\phi = (1+\sqrt 5)/2\approx1.618$ and $\psi = (1-\sqrt 5)/2\approx-0.618$. Since $|\psi|<1$ that term will be negligible for sufficiently large values of $k$ so we have $F_k\approx \phi^k/\sqrt5$. Taking the log (to the base $\phi$) of both sides, we have $\log{F_k}\approx k-\log{\sqrt5}$, so $k$ will be $\log {F_k}$ plus a constant which we can ignore. In terms, then, of its arguments, $p, q$, with $q \ge p$ we'll have our conjecture: $$ T(p, q) = O(\log q) $$ which happens to be true, even if we don't restrict ourselves to Fibonacci numbers for the arguments.

This function is just the timing function for the Euclidean algorithm, which finds the greatest common divisor of the arguments:

gcd(p, q) =
   if p = 0
      return q
   else
      return gcd(q mod p, p)

For instance, $$ \gcd(15, 24) = \gcd(9, 15) = \gcd(6, 9) = \gcd(3, 6) = \gcd(0, 3) = 3 $$ after five recursive calls. It happens that the longest this algorithm will take to complete is when the arguments are consecutive Fibonacci numbers. The upshot is that, fortunately for us this is fast, being no worse than proportional to the number of digits in the arguments.