The Archive

To see problems and solutions in the fall series, which runs from October 13 through December 15 visit The Fall 2025 Featured Problem Series

Problem

This week’s problem comes from Penn State Math 311W, a sophomore-level discrete math course known for its concrete yet challenging problems that do not depend on knowledge of calculus.

The Fibonacci sequence is defined recursively as follows: , and for Show that every two successive terms of the Fibonacci sequence are relatively prime, that is for .

Solution

The proof uses induction.

The base case is . In this case, the definition of the Fibonacci sequence yields Let be a common divisor of and . Although for all , implies that . Hence is the only common divisor of and . In particular, there is no common divisor greater than , consequently . Thus the base case holds.

The induction hypothesis is that for some . It must be shown that the induction hypothesis implies that . The definition of the the Fibonacci sequence is used to write Two properties of the greatest common divisor, and , are used on the right hands side of to obtain where the last equality follows from the induction hypothesis. Equations and together give