Jason Yuan's Math Blogs

Hello and welcome to my first blog post! In this blog I will be sharing different tips and tricks to help you on your math-learning journey, or just tricks I think are cool 🙂.

Anyways, today I will be talking about Counting with Recursion. If you haven’t seen this concept used before, it will blow your mind. If you have seen it used before, I recommend you still stick around because it is really cool. 

Let’s start with a problem from the 2019 AMC 12B:

“How many sequences of 0s and 1s of length 19 are there that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no three consecutive 1s?”

If if you’ve never seen this type of problem before, it may seem daunting. It is, after all, number 23 on the AMC12, a problem most people don’t even take a look at during the allotted 75 minutes. You might try casing on the number of zeros or ones, but that doesn’t seem too promising-after all, how is it humanly possible find all of the combinations when there are 19 digits to arrange? 

When I see these kinds of problems, what I immediately do is look at smaller cases. For this problem, it means looking at sequences with less zeros and ones that satisfy the same condition. This way, it will be easier to calculate the number of “good” sequences and maybe a pattern will emerge. 

For a positive integer n, let’s say f(n) is the number of sequences of zeros and ones that satisfy the problem statement. We can construct a table as follows:

It may take a bit of time, but there aren’t that many cases to go through. Now, is there a pattern? Yes! If you have a keen eye for patterns, you may see that for each f(n) where n is greater than 5, f(n) is equal to f(n-2) + f(n-3). On the actual AMC12, that is good enough. You can assume that the pattern holds and going to n=19 will give you f(19) = 65. But it’s a good learning opportunity to try to justify why this is the case, so here we go!

A valid sequence of length n must be in the form 0…………0. There are 2 cases for the end of the sequence: either it ends with a 010 or a 0110. This means that all sequences that satisfy the first case can be generated by first taking a valid sequence of length n-2 and appending a “10”, and that for the second case, all valid sequences of length n can be generated by first taking a valid sequence of length n-3 and appending a “110”. Therefore, the number of valid sequences of length n is just the sum of the number of valid sequences of length n – 2 and n – 3, or f(n) = f(n – 2) + f(n – 3)!

That was a nice problem! I especially love counting problems like this one that are easy to understand but hard to solve because they are so intuitive. Anyone can figure them out! Anyways, if you liked this blog, make sure to stay tuned for more.