First, let us recall the definition of the Fibonnaci numbers: the first and seco
ID: 647898 • Letter: F
Question
First, let us recall the definition of the Fibonnaci numbers: the first and second Fibonnaci numbers are both 1; the nth Fibonnaci number for n greater than 2 is the sum of the (n-1)th and (n-2)nd Fibonnaci numbers.
Now consider the following function in OCaml that calculates the nth Fibonnaci number
Your task in this problem is to prove that this function is correct, i.e., you need to show
For n greater than or equal to 1, (fib n) evaluates to the nth Fibonnaci number.
The steps through which you should do this are the following:
Identify a property of fib' that will be useful in showing this; recall that this kind of property of auxiliary functions is what we have been calling a "lemma" about them.
Using induction, prove that fib' has this property.
Using the property you have shown fib' to possess, prove that fib has the property that we want to show for it.
Be very careful in picking the property you want to show for fib'. As we saw in the case of tr_fact in class, you need to pick a property that satisfies two different criteria: you must be able to show that fib' possesses it and it must be useful in showing that fib is correct.
Whatever you write for this part should be included in comments in the the hw5.ml file.
Explanation / Answer
(* Naive binary recursion: F(n) = F(n-1) + F(n-2) *) let rec fib = function | 0 -> 0 | 1 -> 1 | n -> fib (n-1) + fib (n-2) (* Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1) *) let f n = (if n -n else fun n -> n) (fib (abs n)) (* entry point *) let _ = (* read the integer argument from command line *) let n = try int_of_string Sys.argv.(1) with _ -> invalid_arg "Usage: f1a " in (* calculate f(n) *) let answer = f n in (* output *) Printf.printf "%dth Fibonacci number is %d " n answerRelated Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.