How 9 Cheenta students ranked in top 100 in ISI and CMI Entrances?
Learn More

Recursion - AMC 10B, 2019 Problem 25

What is Recursion

Recursion is basically an idea of connecting any term with the next or previous term of an series. The most famous example of recursion is Fibonacci series \(0,1,1,2,3,5,8,........\) its recursion formula is \(t_{n+2}=t_{n+1}+t_n\) for natural number n.

Try the problem

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

$\textbf{(A) }55\qquad\textbf{(B) }60\qquad\textbf{(C) }65\qquad\textbf{(D) }70\qquad\textbf{(E) }75$

AMC 10B, 2019 Problem 25


6 out of 10

challenges and thrills of pre college mathematics

Knowledge Graph

Recursion- knowledge graph

Use some hints

We can deduce, from the given restrictions, that any valid sequence of length $n$ will start with a $0$ followed by either $10$ or $110$. Thus we can define a recursive function $f(n) = f(n-3) + f(n-2)$, where $f(n)$ is the number of valid sequences of length $n$.

This is because for any valid sequence of length $n$, you can append either $10$ or $110$ and the resulting sequence will still satisfy the given conditions.

It is easy to find $f(5) = 1$ with the only possible sequence being $01010$ and $f(6) = 2$ with the only two possible sequences being $011010$ and $010110$ by hand, and then by the recursive formula, we have \(f(19)=65\) so option C is correct option.

Subscribe to Cheenta at Youtube

Knowledge Partner

Cheenta is a knowledge partner of Aditya Birla Education Academy

Cheenta Academy

Aditya Birla Education Academy

Aditya Birla Education Academy

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.