Bit-Strings at Bailey Middle School

The Bard Math Circle traveled to Bailey Middle School on Kingston this past Friday; students worked on challenge problems based on a set done in Rhinebeck last April. For one of the problams, students were asked to find how many bit-strings of length n (n-bit strings) there are, given that a single bit is either a 0 or a 1. For example, there are four 2-bit strings (00, 01, 10, 11) and eight 3-bit strings (000, 001, 010, 011, 100, 101, 110, 111).

There are two strategies (maybe more!) that can be used to solve this problem. The first is to write out all of the bit-strings of length 2, 3, 4, etc, and try to find a pattern. The other is to create an algorithm for finding all bit-strings of length m from bit-strings of length m-1, and then write a formula using this information. Can you do it?