Define the Fibonacci numbers by the sequence f1 = 1, f2 = 1, and fn = fn−1 + fn−2 for n ≥ 3. Thus the first several Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .. (We’ll see a lot more...

Define the Fibonacci numbers by the sequence f1 = 1, f2 = 1, and fn = fn−1 + fn−2 for n ≥ 3. Thus the first several Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .. (We’ll see a lot more about the Fibonacci numbers in Section 6.4.) Prove each of the following statements by induction (weak or strong, as appropriate) on n: