Algorithms

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani

Computer Science

1st Edition 路 333 pages

ISBN: 9780073523408

Chapter 1: Q19E (page 49)

The Fibonacci numbers $F_{0}, F_{1}, . ..$ are given by the recurrence $F_{n + 1} = F_{n} + F_{n - 1} 鈥�, F_{0} = 0, F_{1} = 1$ . Show that for any $n 鈮� 1, \gcd (F_{n + 1}, F_{n}) = 1$ .

Short Answer

Expert verified

For any $n 鈮� 1$ , $\gcd (F_{n + 1}, F_{n}) = 1$

Step by step solution

Explain Fibonacci Series

Fibonacci Series is defined as every element of the series is the sum of two previous number of the series. Series starts from 0 and 1.

$\begin{array}{l} F_{n + 1} = F_{n} + F_{n - 1} 鈥� forn = 1 \\ Here, \\ F_{n} isthe 鈥� nthFibonacci 鈥� number \\ F_{0} = 0 \\ F_{1} = F_{2} = 1 \end{array}$

Calculate the gcd by two methods

$\begin{array}{l} GCD for the Fibonacci series, \\ \gcd (F_{1}, F_{0}) \\ = \gcd (1, 0) \\ = 1 \\ Let the \gcd be correct forn = k, that is \\ \gcd (F_{k}, F_{k - 1}) = 1 \\ Prove that the \gcd is also correct forn = k + 1, i . e . \\ \gcd (F_{k + 1}, F_{k}) = 1 \\ \gcd (F_{k + 1}, F_{k}) \\ = \gcd (F_{k} + F_{k - 1}, F_{k}) \\ = 1 \\ So, \gcd (F_{k}, F_{k - 1}) = 1 \end{array}$

$\begin{matrix} Let \gcd (p, q) = 1 鈥� and 鈥� let 鈥� \gcd (p + q, q) = x . Prove that x = 1 \\ \gcd (p + q, q) = x \\ = x | p + 辩脵虫 | q \\ = x | (p + q) - q \\ = x | p and since x | q \\ = x | 1 \\ = x = 1 \\ \gcd (p + q, q) = 1 \end{matrix}$

Thus, $\gcd (F_{n + 1}, F_{n}) = 1$ . Hence proved.

Unlock Step-by-Step Solutions & Ace Your Exams!

Full Textbook Solutions
Get detailed explanations and key concepts
Unlimited Al creation
Al flashcards, explanations, exams and more...
Ads-free access
To over 500 millions flashcards
Money-back guarantee
We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

91影视

The Fibonacci numbers $F_{0}, F_{1}, . ..$ are given by the recurrence $F_{n + 1} = F_{n} + F_{n - 1} 鈥�, F_{0} = 0, F_{1} = 1$ . Show that for any $n 鈮� 1, \gcd (F_{n + 1}, F_{n}) = 1$ .

Short Answer

Step by step solution

Explain Fibonacci Series

Calculate the gcd by two methods

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Game Design in Computer Science

Theory of Computation

Data Structures

Computer Systems

Blockchain Technology

Computer Organisation and Architecture

Study anywhere. Anytime. Across all devices.

91影视

The Fibonacci numbers F0,F1,...are given by the recurrenceFn+1=Fn+Fn-1鈥�,F0=0,F1=1. Show that for anyn鈮�1,gcd(Fn+1,Fn)=1.

Short Answer

Step by step solution

Explain Fibonacci Series

Calculate the gcd by two methods

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Game Design in Computer Science

Theory of Computation

Data Structures

Computer Systems

Blockchain Technology

Computer Organisation and Architecture

Study anywhere. Anytime. Across all devices.

The Fibonacci numbers $F_{0}, F_{1}, . ..$ are given by the recurrence $F_{n + 1} = F_{n} + F_{n - 1} 鈥�, F_{0} = 0, F_{1} = 1$ . Show that for any $n 鈮� 1, \gcd (F_{n + 1}, F_{n}) = 1$ .