Read this supposed proof that \"for all integers n > 0, gcd( F n +1 , F n ) = 1\
ID: 3546507 • Letter: R
Question
Read this supposed proof that "for all integers n > 0, gcd(Fn+1, Fn) = 1":
Match the related questions/answers:
1. The inductive hypothesis.
2. P(k+1)
3. We can conclude that...
4. The basis step. P(0)
Since both the basis and the inductive steps have been proved, we conclude that gcd(Fn+1, Fn) = 1, for all integers n > 0.
Since the inductive step begs the question, we cannot conclude that gcd(Fn+1, Fn) = 1, for all integers n > 0.
gcd(Fk+2, Fk+1) = 1
gcd(Fk+1, Fk) = 1
gcd(F1 , F0) = 1
A.Since both the basis and the inductive steps have been proved, we conclude that gcd(Fn+1, Fn) = 1, for all integers n > 0.
B.Since the inductive step begs the question, we cannot conclude that gcd(Fn+1, Fn) = 1, for all integers n > 0.
C.gcd(Fk+2, Fk+1) = 1
D.gcd(Fk+1, Fk) = 1
E.gcd(F1 , F0) = 1
Proof (by mathematical induction): Let the property P(n) be the equation (Fn + l, Fn) = 1. Show that P(0) is true: To prove the property for n = 0, we must show that gcd(F1, F0) = 1. But F1 = 1 and F0 = 1 and gcd(1, 1) = 1. Show that for all integers k 0, if P(k) is true then P(k + 1) is true: Let k be any integer with k 0, and suppose that gcd(Fk+1, Fk) = 1. We must show that gcd(Fk+2, FK+1) = 1. But by definition of the Fibonacci sequence Fk+2 = Fk+1 + Fk. It follows from Lemma 4. 8. 2 that gcd(Fk+2, Fk+1) = gcd(Fk+1,Fk). But by inductive hypothesis, gcd(Fk+1, Fk) = 1. Hence gcd(Fk+2, Fk+1) = 1 [as was to be shown].
Explanation / Answer
1. D
2. C
3. A
4. E
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.