Count binary strings for which length plus number of ones equals n. Different lengths are allowed.
Quant ResearchLevel: IntermediateWeighted binary strings
Count binary strings for which length plus number of ones equals n. Different lengths are allowed.
Hints
- Translate each symbol into a contribution to n.
- Split by the last symbol.
Answer
A zero consumes weight 1 and a one weight 2. The final symbol gives a_n=a_(n-1)+a_(n-2), with a0=1 and a1=1. Thus a_n=F_(n+1). This is counting compositions of n into 1s and 2s, not fixed-length bit strings.
Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial