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.
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
Recursion
6 out of 10
challenges and thrills of pre college mathematics
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.
I.S.I. & C.M.I. Entrance Program
Taught by students and alumni of I.S.I. & C.M.I.
In 2026, the following Cheenta students have been successful for Indian Statistical Institute's M.Stat Entrance. They ranked within the first 50 in the entire country in these entrances. I.S.I. M.Stat Entrance
In 2026, the following Cheenta students have been successful for Indian Statistical Institute's B.Stat Entrance and Chennai Mathematical Institute's B.Sc. Math Entrance. They ranked within the first 200 in the entire country in these entrances. Most of these students attended the problem solving workshops regularly, which happen 5 days every week. CMI B.Sc. Math Entrance […]
In 2025, 8 students from Cheenta Academy cracked the prestigious Regional Math Olympiad. In this post, we will share some of their success stories and learning strategies. The Regional Mathematics Olympiad (RMO) and the Indian National Mathematics Olympiad (INMO) are two most important mathematics contests in India.These two contests are for the students who are […]
Cheenta Academy proudly celebrates the success of 27 current and former students who qualified for the Indian Olympiad Qualifier in Mathematics (IOQM) 2025, advancing to the next stage — RMO. This accomplishment highlights their perseverance and Cheenta’s ongoing mission to nurture mathematical excellence and research-oriented learning.