2
$\begingroup$

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:

enter image description here

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.

$\endgroup$
5
  • 3
    $\begingroup$ Fibonacci[#+2]& $\endgroup$
    – ciao
    May 4 '20 at 21:54
  • $\begingroup$ @ciao could you explain? I am new to this and some syntax is still strange to me. Thanks :) $\endgroup$
    – tavalendo
    May 4 '20 at 21:55
  • 1
    $\begingroup$ 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). $\endgroup$
    – ciao
    May 4 '20 at 22:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – MarcoB
    May 4 '20 at 22:14
  • 1
    $\begingroup$ 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[]. $\endgroup$
    – J. M.'s torpor
    May 5 '20 at 1:15
6
$\begingroup$

Per comment:

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

enter image description here

$\endgroup$
5
$\begingroup$

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}],
  TableHeadings -> {None, {"m", "seq"}}
]

table of correct values for relation

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]"}}
]

comparison with Fibonacci sequence


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])}} *)
$\endgroup$

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.