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

  • 1
    $\begingroup$ 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$. $\endgroup$ – 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


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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.