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 \geq 1, \gcd (F_{n + 1}, F_{n}) = 1$ .

Short Answer

Expert verified

For any $n \geq 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 | 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.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

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.

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 \geq 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

Problem Solving Techniques

Issues in Computer Science

Big Data

Computer Organisation and Architecture

Computer Network

Game Design in Computer Science

Study anywhere. Anytime. Across all devices.

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

Problem Solving Techniques

Issues in Computer Science

Big Data

Computer Organisation and Architecture

Computer Network

Game Design in Computer Science

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 \geq 1, \gcd (F_{n + 1}, F_{n}) = 1$ .