# Counting the number of binary strings of length m with no consecutive 1s (RR). How to improve it?

I am new to Mathematica and I am trying to solve this problem of counting the number of binary strings of a certain length m, as far as no consecutive 1s are there.

For instance m = 3, my recurrence relation should give 5 i.e. 000, 001, 101, 100, 010.

I started like this with initial seeds: n > 0; a[ 1] = 1, a[2] = 3, a[3] = 5 and then in RSolve I did:

Is there a better way to improve it so that I can use the output in a plot? Currently, I cannot as my solution says it cannot be used as function.

Thanks.

• Fibonacci[#+2]&
– ciao
May 4 '20 at 21:54
• @ciao could you explain? I am new to this and some syntax is still strange to me. Thanks :) May 4 '20 at 21:55
• That is a pure function, so you'd use it like so Fibonacci[#+2]&[somevalue] where somevalue is your input. If you're just plotting, simpler to just plot Fibonacci[x+2] directly for the range of x (lengths of binary string) you're after. (See my answer for example).
– ciao
May 4 '20 at 22:07
• Note that you should use == and not = to define equations. The latter is for assignments instead. Note also that your initial conditions are inconsistent with your definition: a[3] should be a[2]+a[1] according to your recurrence equation, which should be equal to 4, but you define it equal to 5 instead. May 4 '20 at 22:14
• I note that a is colored black in your screenshot, which means it already had a previous value assigned (likely due to your error of using) = instead of == within RSolve[]. May 5 '20 at 1:15

Per comment:

DiscretePlot[Fibonacci[x + 2], {x, 1, 5},
AxesLabel -> {"String Length", "Number with no 1 runs"}]


First off, you should use == and not = to define equations. The latter is for assignments.

Note also that your initial conditions are inconsistent with your definition: a[3] should be a[2]+a[1] according to your recurrence equation, i.e. 4, but you correctly define it equal to 5.

Let's check what the correct numbers should be by construction. For each value of $$m$$ we construct all possible runs of $$m$$ binary digits as a list (Tuples), then discard those with runs of ones (DeleteCases), then count the remaining ones (Length), and list those counts as a function of the number of digits:

TableForm[
Table[{m, Length@DeleteCases[Tuples[{0, 1}, {m}], {___, 1, 1, ___}]}, {m, 5}],
]


As @ciao insightfully pointed out, this can be expressed as Fibonacci[m + 2]:

TableForm[
Table[{m, Length@DeleteCases[Tuples[{0, 1}, {m}], {___, 1, 1, ___}], Fibonacci[m + 2]}, {m, 5}],
TableHeadings -> {None, {"m", "seq", "Fibonacci[m+2]"}}
]


With the correct boundary values, RSolve does return a solution, but not as one as straightforward as the one @ciao found:

RSolve[
{a[n] == a[n - 1] + a[n - 2], a[1] == 2, a[2] == 3, a[3] == 5},
a[n], n
]

(* Out: {{a[n] -> (1/2)*(3 Fibonacci[n] + LucasL[n])}} *)