In: Advanced Math
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:
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 21 = 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) = 2k .f(0)
Since from the basic step we know that f(0) = 2.
f(k + 1) = 2k.2 = 2k+1
Thus we have proved that the number of ways you can form a "word" of length k+1 is 2k+1.
Hence, proof by induction is complete.
.