Question 1 (Fibonacci Numbers, 10 points). Suppose that we have a sequence Fn defined by Fi...

Transcribed Image Text:

Question 1 (Fibonacci Numbers, 10 points). Suppose that we have a sequence Fn defined by Fi = F₂= 1 and for n ≥ 3 we have that Fn = Fn-1 + Fn-2 Consider the following purported proof that Fn =O (1) by induction: If n = 1, then F₁ = 1 = 0 (1). If n = 2, then F₂ = 1 = 0 (1). Otherwise, assuming that Fm = 0 (1) for all m<n we have Fn = Fn-1 + Fn-2= 0 (1) +0 (1) = 0 (1). Thus, Fn = 0 (1) for all n. What is wrong with this proof? Hint 1: Consider the implied constants in the big Os. Hint 2: The principle of Mathematical Induction is a principle that says that for any statement P(n) if it is true for any arbitrary value 'a'if P(a) is true and if we take P(k) to be true then by proving P(k+1) to be true we can prove that P(n) to be true for all n ≥a, and n belonging to Natural numbers. Question 1 (Fibonacci Numbers, 10 points). Suppose that we have a sequence Fn defined by Fi = F₂= 1 and for n ≥ 3 we have that Fn = Fn-1 + Fn-2 Consider the following purported proof that Fn =O (1) by induction: If n = 1, then F₁ = 1 = 0 (1). If n = 2, then F₂ = 1 = 0 (1). Otherwise, assuming that Fm = 0 (1) for all m<n we have Fn = Fn-1 + Fn-2= 0 (1) +0 (1) = 0 (1). Thus, Fn = 0 (1) for all n. What is wrong with this proof? Hint 1: Consider the implied constants in the big Os. Hint 2: The principle of Mathematical Induction is a principle that says that for any statement P(n) if it is true for any arbitrary value 'a'if P(a) is true and if we take P(k) to be true then by proving P(k+1) to be true we can prove that P(n) to be true for all n ≥a, and n belonging to Natural numbers.

Answer rating: 100% (QA)

The image contains a question about the Fibonacci sequence where ... View the full answer