Special Topics putting a T at then end of any sequence in Sn-1 gives a sequence in Sn. Therefore, the number of sequences in the first group is exactly equal to ISn-1l How many sequences are there in the second group? Arguing as before, the preceding 2 symbols in each such sequence must form a sequence in Sn-2. On the other hand, appending TH to any sequence in Sn-2 gives a sequence in the second group. Therefore, there are exactly [Sn-2 sequences in the second group SnI= Sn-1+Sn-2+Sn-3+Sn-4+Sn-(for n>5) This recurrence equation expresses the solution to a large problem(ISn) in terms of the solutions to smaller problems(Sn-1,Sr By combining the base cases and the recurrence equation, we can compute S6l, IS I Ssl, and so forth until we reach Stool S6|=|Ss|+|S4|+|S3|+|S2|+|S1 31+16+8+4+2+1 Sr|=|S6|+|S+|S4|+|S3|+|S2 62+31+16+8+4+2 123 Computing S1ool still requires about 500 additions, so a computer helps. Plugging the value of Shoo into our earlier probability formula, we find Pr(sequence has no HHHHH)=0.193 Thus, four out of five sequences of 100 coin tosses contain a streak of five heads. By symmetry, we also know that four out of five sequences contain a streak of five tails. If we suppose that these two events are nearly independent, then only about one random sequence in twenty-five contains no streak of five heads or five tails. This is the situation for the sequence given at the start of this section. Sure enough, I made up that sequence up by""tapping keys!Special Topics 3 putting a T at then end of any sequence in Sn−1 gives a sequence in Sn. Therefore, the number of sequences in the first group is exactly equal to |Sn−1|. How many sequences are there in the second group? Arguing as before, the preceding n − 2 symbols in each such sequence must form a sequence in Sn−2. On the other hand, appending TH to any sequence in Sn−2 gives a sequence in the second group. Therefore, there are exactly |Sn−2| sequences in the second group. By similar reasoning, the number of sequences in the third group is |Sn−3|, the number in the fourth is |Sn−4|, and the number in the fifth is |Sn−5|. Therefore, we have: |Sn| = |Sn−1| + |Sn−2| + |Sn−3| + |Sn−4| + |Sn−5| (for n > 5) This recurrence equation expresses the solution to a large problem (|Sn|) in terms of the solutions to smaller problems (Sn−1, Sn−2, ...). By combining the base cases and the recurrence equation, we can compute |S6|, |S7|, |S8|, and so forth until we reach |S100|. |S6| = |S5| + |S4| + |S3| + |S2| + |S1| = 31 + 16 + 8 + 4 + 2 + 1 = 62 |S7| = |S6| + |S5| + |S4| + |S3| + |S2| = 62 + 31 + 16 + 8 + 4 + 2 = 123 |S8| = ... Computing |S100| still requires about 500 additions, so a computer helps. Plugging the value of |S100| into our earlier probability formula, we find: Pr (sequence has no HHHHH) = 0.193 ... Thus, four out of five sequences of 100 coin tosses contain a streak of five heads. By symmetry, we also know that four out of five sequences contain a streak of five tails. If we suppose that these two events are nearly independent, then only about one random sequence in twenty-five contains no streak of five heads or five tails. This is the situation for the sequence given at the start of this section. Sure enough, I made up that sequence up by “randomly” tapping keys!