IGNOU MTE 13 2018 - Let fn denote the nth Fibonacci number. Show by induction that every n

Question

Let f_n denote the n^th Fibonacci number. Show by induction that every natural number is expressible as a sum

f_n1 + f_n2 + .......+ f_nk

where n_i - n_i+1 > 1 for each i > 1.

14 Feb 2018

Answer :

Word Count : 354

This problem is related to the Zeckendorf's Theorem, which states that every natural number can be uniquely expressed as a sum of non-consecutive Fibonacci numbers. ### Inductive Proof We need to prove that every natural number can be represented as a sum of Fibonacci numbers where no two are consecutive. #### Base Cases: 1. \( n = 1 \), we have \( 1 = F_2 \) (since \( F_1 = 1, F_2 = 1 \), but we choose \( F_2 \) for uniqueness). 2. \( n = 2 \), we have \( 2 = F_3 \). 3. \( n = 3 \), we

_______ __________ ________ _________ _____.
___ _______ ______ ___ ________ __________ ______ _________ __________ ________.
________ _________ ________ __________ ___ _____ _________ _____.
__________ _________ ______ ______ ____ ___.
__________ ____ ________ ________ _____ _______ _______.
___ ______ __________ _______ ______ ___ ________.
_________ _________ ________ _________ ______ ___ __________ _____ ______ ________ ________ _______.
_____ ______ ___ __________ __________ _____.
__________ _________ __________ _____ ___ ____ _________ _______.
_______ ______ ________ _______ ________ __________ _____ __________ __________.
______ ______ ______ ______ ______ _______ _________.
_______ _____ _____ __________ _______ _______ _____ _______ _____.
__________ ______ _______ __________ ____.
______ _____ _______ ________ ___ _______ _____ _____.
___ ________ _______ ______ _________ ____ ______ __________ ______.
___ __________ _____ ____ ______ _____ ____ _________ ______ __________ ____ ______.
______ __________ _________ _____ _________ ____ ________ _________ ____ ______ _________.
____ _______ ______ __________ _______ ______ _________ ____ ___.
___ ____ _______ ____ _______.
____ _______ _______ _____ ________ _____ _______ __________ _______ ______ __________ _______.
___ _______ ___ ___ _______ ______ ________.
___ ______ __________ ___ ______ _________ _____ ___ _______ __________.
___ ____ ________ _________ ___ _________ _________ ______ ____ ________ ____ ______.
___ _________ _________ ____ _______.
________ _____ ___ ______ _________ _____ _________ _______ ___ ___ ________.
__________ ________ __________ ________ __________ ______ ___ ________.
__________ __________ _____ ___ _________ ________ ___ ___ ________.
_____ ___ __________ ________ ______ ___.
________ ___ __________ ___ _______ _____ ________.
_______ _________ ________ ________ _______ _______ __________.
_______ ___ ______ _________.

IGNOU ACADEMY

Your IGNOU journey, made easier.

Solved Assignments
Study Notes
Guess Papers
Question Papers

Call Us WhatsApp

STUDY • PREPARE • SUCCEED

Skip in 10