Remeber how the Fibonacci numbers can be described by (fn = fn-1 + fn-2 when n >=2). Let the attached image be the generating function (F(x)) for this sequence. If A ⊆ n that is consecutive for all k natural numbers with k, k+1 being in A. Then B ⊆ n is nonconsecutive if this does not happen. (Ex. {1, 4, 8, 9} = consecutive; {2, 5} = nonconsecutive; {0} = nonconsecutive) (a) What is a closed formula of F(x) and what is a closed formula for fn? (b) Prove that there exists fn+2 nonconsecutive subsets of n for all n in the natural numbers. (Let fk stand for the k-th term in the Fibonacci sequence.)
Remeber how the Fibonacci numbers can be described by (fn = fn-1 + fn-2 when n >=2). Let the attached image be the generating function (F(x)) for this sequence. If A ⊆ n that is consecutive for all k natural numbers with k, k+1 being in A. Then B ⊆ n is nonconsecutive if this does not happen. (Ex. {1, 4, 8, 9} = consecutive; {2, 5} = nonconsecutive; {0} = nonconsecutive)
(a) What is a closed formula of F(x) and what is a closed formula for fn?
(b) Prove that there exists fn+2 nonconsecutive subsets of n for all n in the natural numbers. (Let fk stand for the k-th term in the Fibonacci sequence.)
In this problem, we explore the relationship between the Fibonacci sequence and nonconsecutive subsets of natural numbers.
We start by finding a closed formula for the generating function F(x) of the Fibonacci sequence, and then use this formula to derive a closed formula for the nth term fn.
In part (b), we prove that there exist fn+2 nonconsecutive subsets of n for all n in the natural numbers using strong induction.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
