I'm a bit stuck on this problem and can't figure out how to proceed. We have the following Fib. recurrence given to us:
$f(0;a,b) = a;$
$f(1;a,b) = b;$
$f(n;a,b)=f(n-1;b, a+b)$
The problem defines a function $L(a,b)=(b,a+b)$.
It then says "Then $f(n;a,b)$ can be seen as $(L^n(a,b))_1$, which means that the answer is the first number in the pair $(a,b)$. It says
Prove using mathematical induction for any $n \in \mathbb{N}, L^n(a,b)=(f(n;a,b), f(n + 1; a,b))$.
I can solve the first part where the assumption is that n=1 holds true:
$L^1(a,b) = (f(1; a,b), f(2; a, b)) = (b, f(a; b, a+b)) = (b, a+b)$
I assume this is correct because the answer I got, ($(b, a+b)$), is given as the definition of the function $L$.
Then I assume that $L^k(a,b)=(f(k;a,b), f(k+1;a,b))$.
Here's where I am stuck. The farthest I have gone is this:
$L^{k+1}(a,b)=L^k * L^1 = (f(k;a,b), f(k+1;a,b)) * (b, a+b)$
I'm not really sure where to go from here... I don't know how to multiply a function $f$ by a variable $b$ or $a+b$ and return another function that can prove that it is true for $k+1$. Would anyone be willing to give me a hint on how to proceed?
$$L^k(a,b)=(f(k;a,b), f(k+1;a,b))$$ $$L^{k+1}(a,b)=L(f(k;a,b), f(k+1;a,b))=(f(k+1;a,b), f(k;a,b)+ f(k+1;a,b))$$ $$=(f(k+1;a,b), f(k+2;b,a+b))$$ $$\therefore L^{k+1}(a,b)=(f(k+1;a,b), f((k+1)+1;b,a+b))$$ This completes the induction.