Consider the following version of the Fibonacci sequence starting from Fo = 0 and defined by: Fo=0 F1 = 1 Fibonacci Sequence Fn+2= Fm+1 + Fun20: Prove the following identity, for any fixed k > 1 and all n 20, Fn+x= FxFn+1 + Fx-1 FM The Fibonacci Sequence 0,1,1, 2, 3, 5, 8, 13, 21, 34, 55... Assertion: Fn+x=FxFn+1 + F:-1Fn, for any fixed k 2 1 and all n > 0 k=1, 1=0 Fi=FF: + FoFo = 1 k=1, n=1 Fo=F1 F2 + FoFi =? 1 = 1*1 + 0*1 = 1 k=5, n=4 F=FF: + F.F. = 5*5 +3*3 = 34 Assumption for pair (ka: k> 1, n > 0) assertion is valid. Is this identity true for n+1, k+1? Fm+*+2=Fx+1Fn+2+ FxFn+1 ?? True