Length 1: 0, 1
Length 2: 00, 10, 01, 11
There is a useful recursive technique for finding all strings of length n + 1 given the strings of length n. To do this, we can essentially take the first set of strings and concatenate a 0 or a 1 onto it. Give the previous example with strings of length 1 and strings of length 2 we can demonstrate the following:
Now, let's take a look at a proof by induction which proves this concept.
Prove that there are 2n binary strings of length n.
Proof by induction on n.
Base case: For λ, the length of λ represented as |λ| = 0. This means that is 1 string of length 0 because 20 = 1. There is 2 binary strings of length 1 because we can choose only 0 or 1, and 21 = 2. There are 4 binary strings of length 4 because out options are "00", "10", "01", and "11", and 22 = 4.
Based on this pattern we can see a rule that there are 2n binary strings of length n.
Inductive case: Assume that there are exactly 2n binary strings of length n. Let P(n) = 2n. Consider all the binary strings of length n+1. Each string is either in the form w0 or w1, where w is a string of length n. Then, there are exactly two strings of length n+1 for each string of length n. This means that the number of strings of length n+1 is 2 * 2n = 2n+1. This means that P(n+1) is true because P(n+1) = 2n+1.
By the proof of mathematical induction, there are 2n binary strings of length n.
