 # A bit-string is simply a finite sequence of zeroes and ones. For the purposes of this problem, strings will always have length >= 1, i.e. no zero-length strings. anudoneddbv 2022-07-18 Answered
Discrete Math Recursive Definition
A bit-string is simply a finite sequence of zeroes and ones. For the purposes of this problem, strings will always have length $\ge 1$, i.e. no zero-length strings.
Let ${A}_{n}$ be the number of strings of length n that have no two consecutive zeros. Thus ${A}_{1}=2$ and ${A}_{2}=3$ (strings 01, 10 and 11).
Give recursive definitions for ${A}_{n}$.
$A\left(n+1\right)=A\left(n\right)+A\left(n-1\right),$
$A\left(n\right)=A\left(n-1\right)+A\left(n-2\right).$
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Danica Ray
Step 1
I assume ${A}_{n}$ to be the actual sets not just their respective size.
Step 2
${A}_{n+2}$ equals the disjoint union of the set X of sequences ending in 1 and the set Y of sequences ending in 10. ${A}_{n+1}$ maps bijectively on X via $\left({x}_{1},\dots ,{x}_{n+1}\right)↦\left({x}_{1},\dots ,{x}_{n+1},1\right)$ and ${A}_{n}$ on Y via $\left({x}_{1},\dots ,{x}_{n}\right)↦\left({x}_{1},\dots ,{x}_{n},1,0\right)$.