Recall that the Fibonacci numbers are defined by the following recurrence: Fo = 0 F1 = F = 1, and Fi-1+Fi-2 for i > 2. Prove that for any n 2, the nth Fibonacci number equals the element in the first row and first column of the 2 x 2 matrix A, where A" is the nth power of the following 2 x 2 matrix: n times ^=(16) A 0 Recall that A" = AxAxx A. (Hint: Compute A, A, and A4 to identify a pattern and a general formula for A", and then prove using induction that A" equals the formula you found.)