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


*

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


*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? 
 A: 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)$
