Proof Fibonacci derivation

Can be this done with induction?

It can. More specifically, it can be done with strong induction on two variables. First I suggest looking at https://math.stackexchange.com/a/7665/146030 and thinking of why, in both cases, the first three statements implies the fourth.

We will prove the claim that

$$f(n+m+2)=f(n+1)f(m+1)+f(n)f(m).$$

To begin we define the fibonacci sequence as

\begin{align} f(0)&=0 \\ f(1)&=1 \\ f(n)&=f(n-1)+f(n-2), \text{for } n\ge2. \end{align}

When $n=0$ and $m=0$ then

\begin{align} f(n+m+2) &= f(2) \\ &= 1 \\ &= 1 \cdot1 + 0\cdot0 \\ &= f(1)f(1)+f(0)f(0) \\ &= f(n+1)f(m+1)+f(n)f(m) \end{align}

and so the statement is true when $n=m=0$.

To prove the statement true for all nonnegative $n,m$, we first induct on $n=k$ for a fixed $m$. Assume the statement true for all $0\leq k\leq n$. We now prove the statement for $k+1$.

\begin{align} f((k+1)+m+2) &= f(k+m+3) \\ &= f(k+m+2) + f(k+m+1) \\ &= f(k+m+2) + f((k-1)+m+2) \\ &= \big[f(k+1)f(m+1)+f(k)f(m)\big] + \big[f(k)f(m+1)+f(k-1)f(m)\big] \\ &= \big[f(k+1)f(m+1)+f(k)f(m+1)\big] + \big[f(k)f(m)+f(k-1)f(m)\big] \\ &= \big[f(k+1)+f(k)\big]f(m+1) + \big[f(k)+f(k-1)\big]f(m) \\ &= f(k+2)f(m+1) + f(k+1)f(m) \\ &= f((k+1)+1)f(m+1) + f(k+1)f(m) \end{align}

And so by mathematical induction the statement is true for all $n$ and that fixed $m$. We can see that a similar inductive proof works for a fixed $n$ and $m=k$. Thus we can conclude the statement is true.