Let's define $f(k, n)$
$f(0, n) = f(0, n - 1) + f(1, n - 1)$
$f(1, n) = f(0, n - 1)$
$f(k, 1) = 1$, for every $k$.
$k$, $n$ $\subset \mathbb N$, for $0 \le k \le 1, n \ge 1$.
I noted that $f(k, n) =\operatorname{fibonacci}(n)$, for every $k$ and $n$, as long as we define $\operatorname{fibonacci}(1) = 2$, $\operatorname{fibonacci}(2) = 3$.
$$\operatorname{fibonacci}(n) = \operatorname{fibonacci}(n - 1) + \operatorname{fibonacci}(n - 2)\quad,\quad \operatorname{for} n \gt 2$$
How can I prove that?
You didn’t specify initial conditions, so I set $f(0,1)=a$ and $f(1,1)=b$. Here’s a table of the first few values:
$$\begin{array}{rcc} n:&1&2&3&4&5&6\\ f(0,n):&a&a+b&2a+b&3a+2b&5a+3b&8a+5b\\ f(1,n):&b&a&a+b&2a+b&3a+2b&5a+3b \end{array}$$
At this point it’s easy to conjecture that $f(0,n)=F_na+F_{n-1}b$, where the $F_n$ are the usual Fibonacci numbers with $F_0=0$ and $F_1=1$. This is easily proved by induction. To get the induction off the ground, we observe that
$$f(0,1)=a=F_1a+F_0b$$
and
$$f(0,2)=a+b=F_2a+F_1b\;.$$
If $m\ge 3$, and the conjecture holds for $1\le n<m$, then
$$\begin{align*} f(0,m)&=f(0,m-1)+f(1,m-1)\\ &=f(0,m-1)+f(0,m-2)\\ &=(F_{m-1}a+F_{m-2}b)+(F_{m-2}a+F_{m-3}b)\\ &=F_ma+F_{m-1}b\;, \end{align*}$$
as desired.
Of course we always have $f(1,n)=f(0,n-1)=F_{n-1}a+F_{n-2}b$.
If $a=b=1$, then $f(0,n)=F_n+F_{n-1}=F_{n+1}$, which is what you observed; in this case $f(1,n)=F_n$.