Prove equivalence of two Fibonacci procedures by induction?

Question

I want to prove equivalence of the following Fibonacci procedures using proof by induction.

1. version: $$\text{fib_v1}(n) = \text{fib_v1}(n-1) + \text{fib_v1}(n-2)$$

, with base cases $\text{fib_v1}(0) = 0$ and $\text{fib_v1}(1) = 1$.

2. version:

$$\text{fib_v2}(n, a_0, a_1) = \text{fib_v2}(n-1, a_1, a_0+a_1)$$

, with base case $ \text{fib_v2}(0, a_n, a_{n-1}+a_n) = a_n$, and initial values of the accumulators $a_0 = 0$ and $a_1 = 1$.

The claim is $\text{fib_v1}(n) = \text{fib_v2}(n, a_0, a_1)$, which is easily seen to be true for $n = 0$.

However, I'm completely stuck in the induction case.

Can anyone help?

Answer 1

Let me first save some writing by saying $f_1 = fib_{v1}$ and $f_2 = fib_{v2}$

I think you are stuck because the claim you try to prove: $f_2(n,a_0,a_1) = f_1(n)$ is only true for $a_0 = 0$ and $a_1 = 1$. The claim is not true for other values of $a_0$ and $a_1$.

The claim you really want to prove is that for all $n$, $a_0$, and $a_1$:

$f_2(n,a_0,a_1) = a_0$ (for $n = 0$) and

$f_2(n,a_0,a_1) = f_1(n-1)*a_0 + f_1(n)*a_1 $ (for $n>0$)

Proof:

Base: n=0 Then $f_2(n,a_0,a_1) = a_0$ by definition of $f_2$

Step: Assume the claim holds for $n=k$

Now consider $n = k+1$:

$f_2(k+1,a_0,a_1) =$ (definition $f_2$)

$f_2(k,a_1,a_0 + a_1) =$ (inductive hypothesis)

$f_1(k-1) * a_1 + f_1(k) * (a_0 + a_1) =$

$f_1(k-1) * a_1 + f_1(k) * a_0 + f_1(k) *a_1 =$

$f_1(k) * a_0 + (f_1(k-1) + f_1(k)) *a_1 =$ (definition $f_1$)

$f_1(k)*a_0 + f_1(k+1)*a_1 $

which is exactly what we needed to show.

Finally, now that you know this for any $a_0$ and $a_1$, we can infer as a special case:

$f_2(0,0,1) = 0 = f_1(0)$ and

$f_2(n,0,1) = f_1(n-1)*0 + f_1(n)*1 = f_1(n)$ (for $n>0$)

Hence, for any $n$: $f_2(n,0,1) = f_1(n)$