Binary strings of length n

Length 0: λ (lambda, the empty string)
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 2ⁿ 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 2⁰ = 1. There is 2 binary strings of length 1 because we can choose only 0 or 1, and 2¹ = 2. There are 4 binary strings of length 4 because out options are "00", "10", "01", and "11", and 2² = 4.

Based on this pattern we can see a rule that there are 2ⁿ binary strings of length n.

Inductive case: Assume that there are exactly 2ⁿ binary strings of length n. Let P(n) = 2ⁿ. 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 * 2ⁿ = 2ⁿ⁺¹. This means that P(n+1) is true because P(n+1) = 2ⁿ⁺¹.

By the proof of mathematical induction, there are 2ⁿ binary strings of length n.