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:

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

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


2 Answers 2


(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$.

  • $\begingroup$ what are the preconditions and postconditions? $\endgroup$ Aug 31, 2013 at 4:18
  • $\begingroup$ @winstonsmith For what exactly? For the whole program? For some individual statements? $\endgroup$
    – Juho
    Aug 31, 2013 at 12:56
  • $\begingroup$ for the program? $\endgroup$ Sep 1, 2013 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, 2013 at 15:49

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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