# Proof of a property on a Fibonacci like sequence

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..

• It's probably easier to prove for $n=a+4$ and then if true for $n=k$ then true for $n=k+1$. In other words, easier to prove by induction on $n$, not $a$. – Thomas Andrews Sep 7 '14 at 17:11

say that the statement is true for a certain $a$, we prove it is true for $a+1$:

we start from

$N(n)=N(a+2)N(n−1−a)+N(a)N(n−2−a)+N(a+1)N(n−3−a)$

we assumed $n>a+3$, so we can use $N(n−1−a) = N(n-2-a)+N(n-4-a)$ Substituting this gives:

$N(n)= [N(a+2)+N(a)]N(n-2-a)+N(a+1)N(n-3-a)+N(a+2)N(n-4-a)$

Then we use $N(a+2)+N(a) = N(a+3)$ so:

$N(n)= N(a+3)N(n-2-a)+N(a+1)N(n-3-a)+N(a+2)N(n-4-a)$

this is the statement we had to prove!