A computer calculates the $n$-th Fibonacci Number ($F_n$, where $F_n = F_{n-1} + F_{n-2}$ and $F_0 = 0$, $F_1 = 1$) using "steps". A step is defined to be a single calculation (this means carrying out $a + b$ when we already know $a$ and $b$ counts as one step, though if we don't know what $a$ or$ b$ are, carrying out $a + b$ takes the number of steps to find $a +$ the number of steps to find $b + 1$, with the $1$ coming from calculating $a + b$). The computer can only have $F_0$ and $F_1$ permanently stored, and it has to calculate everything else all over again when a request to calculate a new Fibonacci number is made. The advantage of this process is that the final addition step (to add one due to calculating $a+b$) gets omitted(by some algorithmic magic). In this algorithm, the steps needed to "call" $F_0$ and $F_1$ (these are the only values for which a call counts as a step) are both $1$. Given that the computer can only carry out simple addition of $2$ numbers at most : $\bullet$ Find an expression for $S(F_n)$, the number of steps taken to find $F_n$ using this approach if we can only have $F_0$ and $F_1$ stored for all $n \ge 2$ where $S(F_0) = 1$ and $S(F_1) = 1$ due to the "calling" feature $\bullet$ Find an expression for gcd$(S(F_n), S(F_m)))$ involving only n,m and the gcd function for $n,m \ge 2$ Now, the computer has the ability to "cache" (store) all previously calculated Fibonacci Numbers, but the final step is not omitted anymore. Assuming that we've already calculated Fk for some $2 \le k \le n - 1$, and the probability of picking an Fk is equally likely for all $k$ : $\bullet$ Show that the expected number of steps taken to calculate $F_n$, $E(S(F_n))$, using the "cache" feature (if we have $F_0$ and $F_1$ stored and there is no calling step) is $\frac{n-1}{2}$. Note : $E(X) =\sum P(X = x_i)x_i$ here where $x_i$ is any possible value $X$ can take. Also note that the computer does not know that $F_2 = F_1$ or that $F_0 = 0$.