Categories

## 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

Recursion

6 out of 10

challenges and thrills of pre college mathematics

## 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.