Recursive sequences are sequences of numbers which can be represented by recursive formula. The most famous example continues is a Fibonacci Sequence.

Considerthefollowingsequence$\{$fn $|$n$>=0\}$definedas: f$0=1,$f$1=1,$f$2=2$ and,for i$>2,$ define fi :$=2$f$\_\{$i$1\}+7$f$\_\{$i$2\}+4$ f$\_\{$i$3\}.$

$($a$)$ A common strategy with such recursive sequences is to view it as a matrix multiplication. Let Fi :$=[$ f$\_\{$i$1\}$ f$\_\{$i$2\}$ f$\_\{$i$3]^$T$.$ Then, the recurrence relation can be represented as: A$$F$\_\{$i$1\}=$F$\_$i

How does A need to be chosen in order to represent the recurrence equation from the beginning of the task? Also, for i $>2,$ derive an equation for F$\_$i in terms of F$\_2,$ A$,$ and i$.$ Justify your answers.

$($b$)$ Use part $($a$)$ to build an efficient algorithm that computes f$\_$n$,$ based on the divide and conquer strategy. Note that you are only asked to compute f$\_$n and none of the intermediate values. Your algorithm will derive inspiration from an algorithm discussed in lecture.

Let M$($n$)$ be the number of $3\backslash$times $3$ matrix multiplications performed to compute fn$.$ Derive a recurrence relation for M$($n$)$ with an appropriate base case. You may assume that n $=2$m $+2$ for integer m$.$ Solve it to compute the number of $3\backslash$times $3$ matrix multiplications performed $($asymptotic is fine$).$ Finally, use this value to state an asymptotically tight bound for the running time, assuming that each arithmetic operation performed, i$.$e$.,$ addition and multiplication can be performed in constant time.

$($Hint: You may need a driver function so that only fn value is returned. Your driver function will invoke a recursive algorithm $($say$,$ AExp$).$ Let T $($n$)$ be the number of $3\backslash$times $3$ matrix multiplications to compute AExp$($n$).$ First, formulate a recurrence relation for T $($n$)$ with appropriate base$($s$).$ Then, express M$($n$)$ in terms of the function T with appropriate base case and solve for M $($n$)$ assuming n $=2$m $+2$ for some integer m$.)$

$($c$)$ Prove by induction that, for some constant a $>1,$ f$\_$n $=\backslash$Theta $($a$^$n$).$ Namely, prove by induction that for some constant c$1$ you have f$\_$n $<=$ c$\_1$ a$^$n$,$ and for some constant c$\_2$ you have f$\_$n $>=$ c$\_2$ a$^$n$.$ What is the right constant a and the best c$\_1$ and c$\_2$ you can find. The best c$\_1$ is the smallest possible value for c$\_1,$ and the best c$\_2$ is the largest possible value for c$\_2.$

Based on your results what can you say about the number of bits needs to represent fn$,$ as n grows larger.

$($Hint: Pay attention to the base case n $=0,1,2.$ Also, you need to do two very similar inductive proofs.$)$