4
$\begingroup$

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction.

Here is my recursive version of an algorithm to compute Fibonacci numbers:

Fibonacci(n):
    if n = 0 then     // base case
        return 0
    elseif n = 1 then // base case
        return 1
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2)
    endif

How can I prove the correctness of this algorithm by induction?

$\endgroup$
5
$\begingroup$

(Seems like it may be a duplicate, but the "Related" questions don't seem to be too close, with the possible exception of "this one)

The proof is by induction on $n$. Consider the cases $n = 0$ and $n = 1$. In these cases, the algorithm presented returns $0$ and $1$, which may as well be the 0th and 1st Fibonacci numbers (assuming a reasonable definition of Fibonacci numbers for which these values are correct).

Now, assume that the algorithm returns the correct Fibonacci number for all $n$ (i.e., the nth Fibonacci number) for all $n \leq k$ where $k \geq 1$.

We must show that the algorithm returns the correct value for $k+1$, i.e., the (k+1)th Fibonacci number. By the induction hypothesis, $k \geq 1$, so we are in the else case. We return Fibonacci(k) + Fibonacci(k-1) in this case. By the induction hypothesis, we know that Fibonacci(k) will evaluate to the kth Fibonacci number, and Fibonacci(k-1) will evaluate to the (k-1)th Fibonacci number. By definition, the (k+1)th Fibonacci number equals the sum of the kth and (k-1)th Fibonacci numbers, so we have that the algorithm returns the (k+1)th Fibonacci number on input $k+1$.

The proof of the claim follows by induction on $n$.

$\endgroup$
  • $\begingroup$ what are the preconditions and postconditions? $\endgroup$ – winston smith Aug 31 '13 at 4:18
  • $\begingroup$ @winstonsmith For what exactly? For the whole program? For some individual statements? $\endgroup$ – Juho Aug 31 '13 at 12:56
  • $\begingroup$ for the program? $\endgroup$ – winston smith Sep 1 '13 at 0:03
  • $\begingroup$ @winstonsmith Preconditions and postconditions? The discussion isn't really very interesting for a functional example such as this with no side effects and no free state information. The precondition is that the input is valid, and the postcondition is that the return value is the correct one. $\endgroup$ – Patrick87 Sep 3 '13 at 15:49
4
$\begingroup$

Claim: The algorithm, Fibonacci(n) is correct

(Proof by Strong Induction)

Base Case: for inputs $0$ and $1$, the algorithm returns $0$ and $1$ respectively. So this is Correct.

Induction Hypothesis: Fibonacci(k) is correct for all values of $k \leq n$, where $n,k\in \mathbb{N}$

Inductive Step:

  1. let Fibonacci(k) be true for all values until $n$
  2. From IH, we know Fibonacci(k) correctly computes $F_k$ and Fibonacci(k-1) correctly computes $F_{k-1}$
  3. So, $$ \begin{align*} \text{Fibonacci(k+1)} &= \text{Fibonacci(k) + Fibonacci(k-1)} \\ &\text{(by definition of the Fibonacci function)} \\ \\ &= F_k + F_{k-1} & \\ \\ &= F_{k+1} \\ &\text{(By definition of Fibonacci numbers)}\\ \end{align*} $$

  4. Thus by rules of mathematical Inducion, Fibonacci(n) always returns the correct result for all values of $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.