Recitation 6 3 Problem: The Fibonacci numbers. Again. Give an inductive proof that the Fibonacci numbers Fn and Fn+i are relatively prime for all n>0. Recall that the fibonacci numbers are defined as follows: Fo=0 Fi=1 Fn= Fn-1+ Fn-2(for n> 2) Solution. We use induction on n. Let P(n) be the proposition that Fn and Fn+1 are latively prime Base case P(O)is true because Fo=0 and Fi=l are relatively prime Inductive step: We show that, for all n 20, P(n)implies P(n+1). So, fix some n 20 and assume that P(n) is true, that is, Fn and Fn+1 are relatively prime. We will show that Fn+ and Fn+2 are relatively prime as well. We will do this by contradiction Suppose Fn+1 and Fn+2 are not relatively prime. Then they have a common divisor d> 1. But then d also divides the linear combination Fn+2-Fn+1, which actually equals Hence, d> l divides both Fn and Fn+1. Which implies Fn, Fn+1 are not relatively prime, a contradiction to the inductive hypothesis Therefore, Fn+1 and Fn+2 are relatively prime. That is, P(n+1)is true The theorem follows by inductionRecitation 6 5 3 Problem: The Fibonacci numbers. Again. Give an inductive proof that the Fibonacci numbers Fn and Fn+1 are relatively prime for all n ≥ 0. Recall that the Fibonacci numbers are defined as follows: F0 = 0 F1 = 1 Fn = Fn−1 + Fn−2 (for n ≥ 2). Solution. We use induction on n. Let P(n) be the proposition that Fn and Fn+1 are relatively prime. Base case: P(0) is true because F0 = 0 and F1 = 1 are relatively prime. Inductive step: We show that, for all n ≥ 0, P(n) implies P(n + 1). So, fix some n ≥ 0 and assume that P(n) is true, that is, Fn and Fn+1 are relatively prime. We will show that Fn+1 and Fn+2 are relatively prime as well. We will do this by contradiction. Suppose Fn+1 and Fn+2 are not relatively prime. Then they have a common divisor d > 1. But then d also divides the linear combination Fn+2 − Fn+1, which actually equals Fn. Hence, d > 1 divides both Fn and Fn+1. Which implies Fn, Fn+1 are not relatively prime, a contradiction to the inductive hypothesis. Therefore, Fn+1 and Fn+2 are relatively prime. That is, P(n + 1) is true. The theorem follows by induction