Need help solving and understanding these:

Is there a faster way to compute the nth Fibonacci number than by fib2 (page 13)? One idea involves matrices. We start by writing the equations F1=F1 and F2=F0+F1 in matrix notation: (F1F2)=(0111)(F0F1). Similarly, (F2F3)=(0111)(F1F2)=(0111)2(F0F1) 18 and in general (FnFn+1)=(0111)n(F0F1). So, in order to compute Fn, it suffices to raise this 22 matrix, call it X, to the nth power. (a) Show that two 22 matrices can be multiplied using 4 additions and 8 multiplications. But how many matrix multiplications does it take to compute Xn ? (b) Show that O(logn) matrix multiplications suffice for computing Xn. (Hint: Think about computing X8.)