Let's note that our sequence $f(n)$ satisfies: $f(n)=f(n-k-1)f(k)+f(n-k)f(k+1)$ (it can be checked by induction). We know that there doesn't exist such $n$ that $m|f(n)$ and $gcd(m,f(n+1))>1$ for any $m \in N-\{1\}$, because going backwards recurentially we would obtain $1<gcd(m,f(1))=gcd(m,1)$ what's false. For every $m \in N$ there exists the smallest $k_0 \in N$ such that $m|f(k_0)$. Let's proove that $m|f(n)$ if and only if $k_0|n$. Let's assume that $m>1$ because for $m=1$ there is nothing to proove. Suppose there exists such $t \in N$ that $m|f(t)$ and $k_0$ doesn't divide $t$. Thus we have: $m|f(t)=>m|f(t-k_0-1)f(k_0)+f(t-k_0)f(k_0+1)=>m|f(t-k_0)$, cause $m$ satisfies $gcd(m,f(k_0+1))=1$-what we have already mentioned. So if $m|f(t)$ then $m|f(t-k_0)$. Because $t$ is not divisible by $k_0$ then there exists such $i$ : $i \geq 0$ that $0<t-ik_0<k_0$, so we received a number $t-ik_0$, which is smaller than $k_0$ and satisfies $m|f(t-ik_0)$ - we have a contradiction. Thus we proved that for every $m \in N$ there exists such $k_0 \in N$ that: $m|f(n)$ if and only if $k_0|n$. So $m|f(f(n))$ if and only if $k_0|f(n)$ if and only if $k_1|n$. So our $d$ satisfies: $d=k_1$.

How can $ f(0) = 0$, since codomain is only set of Natural numbers?