Home /
Expert Answers /
Advanced Math /
3-let-fn-be-the-number-of-binary-sequences-sequences-of-ones-and-zeros-of-length-n-for-exam-pa453

3. Let $F_{n}$ be the number of binary sequences (sequences of ones and zeros) of length $n$ (for example 1101 is a binary sequence of length 4). There is a unique sequence of length 0 , the empty sequence. Also having a binary sequence of length $n$ we can obtain one binary sequence of length $n+1$ by adding either a trailing 0 or 1 , so there is always twice as much binary sequences of length $n+1$ than binary sequences of length $n$, i.e., $F_{n+1}=2F_{n}$. Guess a closed formula for $F_{n}$ and prove that the formula is correct using induction. Find a direct proof (without induction) for the closed formula for $F_{n}$ of Problem 3 . [Hint: use the multiplication principle]

Q. 3Answer. There are actually eight three-digit binary numbers, since each position can get two values, hence 2×2×2=8. Your list misses 010.10 is the