A binary string is a “word” in which each “letter” can only be 0or 1
Prove that there are 2^n different binary strings of lengthn.
Note:
- Your goal is to produce a properly constructed proof byinduction, 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=kversion of the statement is true, and using thisassumption to prove that the n=k+1 version of thestatement 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 are2n different binary strings of lengthn” !!! So your solution should primarily be discussingbinary strings. Yes, the fact that2k+1 = 2k?2 willbe useful in your solution, but it should not be the sole contentof your solution, as by itself that equality is a fact aboutexponents, not a fact about binary strings.
