Question

A binary string is a “word” in which each “letter” can only be 0 or 1

Prove that there are 2^n different binary strings of length n.

Note:

• Your goal is to produce a properly constructed proof by induction, but this does not mean you have to follow
• Mathematical induction, step-by-step..
• Write the statement with n replaced by k
• Write the statement with n replaced by k+1.
• Identify the connection between the kth statement and the (k+1)th statement.
• Complete the induction step by assuming that the n=k version of the statement is true, and using this assumption to prove that the n=k+1 version of the statement is true.
• Complete the induction proof by proving the base case.
• point-by-point.
• ANOTHER IMPORTANT NOTE:
• Make sure you are addressing the given statement: "there are 2ⁿ different binary strings of length n” !!! So your solution should primarily be discussing binary strings. Yes, the fact that 2^k+1 = 2^k∙2 will be useful in your solution, but it should not be the sole content of your solution, as by itself that equality is a fact about exponents, not a fact about binary strings.

Answer 1

Step 1: Basic step

for n =1, we can easily see that there are 2 ways to choose the "letters" 0 and 1.

Therefore, the number of ways a "word" of length 1 can be written is 2¹ = 2.

Step 2: Inductive Step

Now for n = k, let function f denote the number of ways you can write a "word" of length k.

Therefore, number of ways you can write the "word" of length k = f(k)

Also, the (k + 1)^th "letter" can either be 0 or 1. Therefore we can write the (k+1)^th letter in 2 ways.

Therefore, the number of ways to write (k + 1) long "word" is 2 .f(k) ways.

Thus, we obtain the relation f(k + 1) = 2 .f(k)

Similarly f(k) = 2.f(k-1)

f(k -1) = 2 .f(k - 2)....

f(1) = 2 .f(0)

Combining the above equations you get , f(k + 1) = 2 * 2 * 2 .....k times * f(0), i.e.

f(k + 1) = 2^k .f(0)

Since from the basic step we know that f(0) = 2.

f(k + 1) = 2^k.2 = 2^k+1

Thus we have proved that the number of ways you can form a "word" of length k+1 is 2^k+1.

Hence, proof by induction is complete.

.