How do we know that these possibilities don't have two whites together for sure?
-
Module 3 Week 3 Day 11 Challenge Part 3 Explanation
How do we know that these possibilities don't have two whites together for sure? I look back at this and I realized that a lot of the video was dedicated to trying to find the end letter (s).
-
@The-Blade-Dancer You've sort of answered your own question.
You are right, a lot of the video is concerned with looking at the last letter of the string of beads. This is actually the principle behind recursion, that you focus on the last step of a sequence rather than worrying about constructing the whole thing from scratch. (The whole "shebang..." )The two main principles of the recursive method are:
1.) Assume that the sequence that you have is already "good."
2.) Now build that sequence to be one bead longer, just being very careful to make sure that the part that you changed (the end) is still "good."
Using the recursive method applied to this beads question is really very freeing, in a sense, because you only have to worry about the very end of the sequence. You just have to make sure you don't mess up and create a white-white at the very end.
Prof. does this by keeping track of how many sequences of length \(n\) end in black, denoted \(B_n,\) and how many sequences of length \(n\) end in white, denoted \(W_n.\) When we build upon this \(n\)-length sequence to make it into an \(n-1\)-length sequence, we just need to make we don't mess up.
\( \rightarrow \textcolor{red}{\text{Just don't add a white bead to a sequence ending in white, and you'll be fine.}} \)
This is the main idea behind how Prof. Loh derived his two recursive formulas,
$$ W_n = B_{n-1} $$
$$B_n = W_{n-1} + B_{n-1}. $$
The first equation says, \( \textcolor{blue}{\text{ "We can only add a white bead to a sequence ending in black," }}\) and the second equation says, \( \textcolor{blue}{\text{ "We can add a black bead to any old sequence." }}\)
Constructing the string of beads in this fashion actually guarantees that there are no whites together!
