Prove that for every integer n 2 0, gcd(Fn + 1, Fn) = 1.
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
![Definition: The greatest common divisor of
integers a and b, denoted gcd(a, b), is that integer
d with the following properties:
1. d divides both a and b.
2. For every integer c, if c divides a and
c divides b, then c < d.
Lemma 4.10.2: If a and b are any integers not
both zero, and if q and r are any integers such that
a = bq + r, then gcd(a, b) = gcd(b, r).
Prove that for every integer n 2 0, gcd(Fn + 1, Fn) = 1.
Proof (by mathematical induction): Let the property P(n) be the equation
gcd(Fn + 1, Fn) = 1.
We will show that P(n) is true for every integer n 2 0.
Show that P(0) is true: P(0) is the equation gcd
= 1. Since F, = 1 and
= 1, then
gcd F1,
= gcd 1,
= 1, as was to be shown.
Show that for every integer 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'
= 1.
+ P(k) inductive hypothesis.
We must show that gcd
= 1.
+P(k + 1).
Now by definition of the Fibonacci sequence, FK + 2 = Fk + 1+
Apply Lemma 4.10.2 with a =
b =
and r =
to conclude that
gcd Fk + 2'
= gcd Fk + 1'
)-
Now, by inductive hypothesis, gcd Fk + 1.
= 1.
Hence gcd
= 1 [as was to be shown].
[Since both the basis and the inductive steps have been proved, we conclude that gcd(F, + 1, Fn) = 1 for every integer n > 0.]](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fba28fbe0-fc04-46bc-bd01-9a9731588fb8%2Fa58c5daa-dc4b-4edc-bb3b-fb22f512e342%2Fz3f9nda_processed.png&w=3840&q=75)
Transcribed Image Text:Definition: The greatest common divisor of
integers a and b, denoted gcd(a, b), is that integer
d with the following properties:
1. d divides both a and b.
2. For every integer c, if c divides a and
c divides b, then c < d.
Lemma 4.10.2: If a and b are any integers not
both zero, and if q and r are any integers such that
a = bq + r, then gcd(a, b) = gcd(b, r).
Prove that for every integer n 2 0, gcd(Fn + 1, Fn) = 1.
Proof (by mathematical induction): Let the property P(n) be the equation
gcd(Fn + 1, Fn) = 1.
We will show that P(n) is true for every integer n 2 0.
Show that P(0) is true: P(0) is the equation gcd
= 1. Since F, = 1 and
= 1, then
gcd F1,
= gcd 1,
= 1, as was to be shown.
Show that for every integer 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'
= 1.
+ P(k) inductive hypothesis.
We must show that gcd
= 1.
+P(k + 1).
Now by definition of the Fibonacci sequence, FK + 2 = Fk + 1+
Apply Lemma 4.10.2 with a =
b =
and r =
to conclude that
gcd Fk + 2'
= gcd Fk + 1'
)-
Now, by inductive hypothesis, gcd Fk + 1.
= 1.
Hence gcd
= 1 [as was to be shown].
[Since both the basis and the inductive steps have been proved, we conclude that gcd(F, + 1, Fn) = 1 for every integer n > 0.]
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
