7.2.2 Fibonacci Numbers Denote the kth Fibonacci number as Fk. These numbers are defined by the rule that the kth number is equal to the sum of the two preceding ones with the initial numbers being Fo = 0 and Fi = 1. They satisfy the following difference equation: FR = Fk-1+ Fk-2- (7.36) This is a second-order, linear difference equation with constant coefficients and can be easily solved. Setting F = rk gives the characteristic equation p2 - r -1= 0, (7.37) whose solutions are 1+ V5 1- V5 r2 = (7.38) 2 2 Consequently, the general solution of equation (7.36) is F = C1 1+ V5 1- V5 + C2 (7.39) 2 The arbitrary constants C1 and C2 may be found by imposing the initial conditions Fo = 0 and F1 = 1. Doing this gives C1 + C2 = 0, (1+ V5)C1 + (1 - V5)C2 = 2, (7.40) which, when solved for C1 and C2, gives 1 C = -C2 = V5 (7.41) APPLICATIONS 219 Putting these values in equation (7.39) gives, for the kth Fibonacci number,