The recurrence relation of the series is the following,
$N(1) = N(2) = N(3) = 1$
$N(n) = N(n-1) + N(n-3)$ for $n>3$
I need to prove by induction on $a$ that,
$N(n) = N(a+2)N(n-1-a) + N(a)N(n-2-a) + N(a+1)N(n-3-a)$
holds for all $a>0$ and $n>a+3$.
The basis step ($a=0$) is easy to show. However the induction step took my hours to figure out. I need some hints.
What I have done:
I calculated the first 20 items of the sequence and tried 4-5 $a$ and $n$ values, and saw that they hold the property.
I tried to prove the claim by assuming it holds for all $a'<a$ and then plugged the definition of the series to the right hand side of the claim. Nothing is getting canceled..