1. Solve some small problems 2. Solve the n-th problem using preceding solutions Lets see how this approach plays out in the analysis of streaks 1. 2 Step 1: Solve Small Instances Let Sn be the set of length-n sequences of H's and T's that do not contain a streak of five heads. Our eventual goal is to compute Soo]. But for now, let's just compute SnI for some very small values of n: Ssss 1= 2(H and T) 4(HH, HT, TH, and TT) 8 Ss|= 31(HHHHH is excluded!) These are called base cases 1. 3 Step 2: Solve the n-th Problem Using Preceding Solutions We can classify the sequences in Sn into five groups 1. Sequences that end with a T 2. Sequences that end with TH 3. Sequences that end with THH 4. Sequences that end with THHH 5. Sequences that end with THHHH Every sequence in Sn falls into exactly one of these groups. Thus, the size of Sn is the sum of the sizes of these five groups How many sequences are there in the first group? That is, how many sequences in Sn end with T? The preceding n- l symbols in such lence can not contain a streak of five heads. Therefore, those n- l symbols form a sequence in Sn-1. On the other hand2 Special Topics 1. Solve some small problems. 2. Solve the n-th problem using preceding solutions. Let’s see how this approach plays out in the analysis of streaks. 1.2 Step 1: Solve Small Instances Let Sn be the set of length-n sequences of H’s and T’s that do not contain a streak of five heads. Our eventual goal is to compute |S100|. But for now, let’s just compute |Sn| for some very small values of n: |S1| = 2 (H and T) |S2| = 4 (HH, HT, TH, and TT) |S3| = 8 |S4| = 16 |S5| = 31 (HHHHH is excluded!) These are called base cases. 1.3 Step 2: Solve the n-th Problem Using Preceding Solutions We can classify the sequences in Sn into five groups: 1. Sequences that end with a T. 2. Sequences that end with TH. 3. Sequences that end with THH. 4. Sequences that end with THHH. 5. Sequences that end with THHHH. Every sequence in Sn falls into exactly one of these groups. Thus, the size of Sn is the sum of the sizes of these five groups. How many sequences are there in the first group? That is, how many sequences in Sn end with T? The preceding n − 1 symbols in such a sequence can not contain a streak of five heads. Therefore, those n − 1 symbols form a sequence in Sn−1. On the other hand