Example 4: Consider the following version of the Fibonacci sequence starting from Fo = 0 and defined by: Fo = 0 F1 = 1 Fibonacci Sequence Fn+2=Fn+1 + Fnin 0: } Prove the following identity, for any fixed k > 1 and all n > 0. Fn+k=FxFn+1 + Fx-1Fn- The Fibonacci Sequence 0,1, 1, 2, 3, 5, 8, 13, 21, 34, 55... Assertion: Fn+x=FxFn+1 + Fk-1 Fr, for any fixed k > 1 and all n > 0 k=1, n=0 Fi= Fi Fi + FoFo = 1 k=l, n=1 F= F1F2 + FoF1 =? 1 = 1*1 +0*1 = 1 k=5, n=4 F = Fs Fs + F4F4 = 5*5 +3*3 = 34 Assumption for pair (k.n: k21, n > 0) assertion is valid. Is this identity true for n+1, k+1? Fn+k+z=Fx+1Fn+2 + FxFn+1 ?? True