Help with Fibonacci Transformation

[Lahooty]

Homework Statement

A more efficient algorithm to calculate Fibonacci numbers applies the simultaneous transformation:

T(a; b) = (a+b; a)

repeatedly with a = 1 and b = 0 as initial values.

What Fibonacci numbers result from T^k(1; 0)? Justify your answer (e.g., as proof by induction in k would be nice).

Homework Equations

The Attempt at a Solution

Let k = 1

T^1(1; 0) = (1; 1) = (F₂; F₁)

Assume T^k(1; 0) = (F_k+1; F_k) and show T^(k+1)(1; 0) = (F_k+2; F_k+1)

T^(k+1)(1; 0) = T^k(T^1(1; 0)) = T^k(1; 1) = (F_k+2; F_k+1)

Is this enough to conclude my solution and justify the proof? Any help will be greatly appreciated.

Thanks

 

[haruspex]

T^k(1; 1) = (F_k+2; F_k+1)

I see no justification for that step. Your inductive hypothesis concerned T^k(1; 0), so you need to derive an expression involving exactly that. Try factorising T^(k+1) differently.