Barcodes are created following the rules:
codes are constructed from white and black bars, each bar 1 or 2 units wide
black and white bars are set alternately
each code begins and ends with a black bar
Find the recursive formula for the number of codes of width n. Width equals sum of all widths of the bars.
I found a solution that might be correct. Suppose the number of barcodes of width n equals f(n). Then:
$f(0)=0$
$f(1)=1$ (b)
$f(2)=1$ (bb)
$f(3)=1$ (b-w-b)
Now let's consider 4 cases:
Case 1: Code starts and ends with a black bar of width 1. Notice that between them we have another code of width n-2 which has to begin and end with white bars. If we reverse its colour it has black bars on its edges. So, the number of codes in this case equals f(n-2).
b-(reversed code of n-2 width)-b
Cases 2,3,4: (by analogy)
bb - (reversed code of n-3 width) - b
b - (reversed code of n-3 width) - bb
bb - (reversed code of n-4 width) - bb
So we sum up all the cases:
$f(n)=f(n-2)+2f(n-3)+f(n-4), n>3$