I was wondering how to prove that
$$f(n+m+2) = f(n+1)f(m+1) + f(n)f(m)$$
where $f$ is the fibonacci sequence and n, m are positive integers.
Can be this done with induction?
I'm lost with this method of proof, because there are two variables.
Any idea or suggestion is welcome.
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.