[JEE Advanced 2012] (Paragraph) $a_n$ = number of $n$-digit positive integers from $\{0,1\}$ with no consecutive $0$s; $b_n$ end in $1$, $c_n$ end in $0$. Establish the recurrences.
(Paragraph) $a_n$ = number of $n$-digit positive integers from $\{0,1\}$ with no consecutive $0$s; $b_n$ end in $1$, $c_n$ end in $0$. Establish the recurrences.
1 Answer
VAVidaara Admin
✓ Vidaara Team
✓ Accepted
· 1mo ago
▲ 0
Answer: $a_n=a_{n-1}+a_{n-2}$ (Fibonacci), with $b_n=a_{n-1}$ and $c_n=b_{n-1}$.
A valid string ending in $1$ extends any valid $(n-1)$-string ($b_n=a_{n-1}$); one ending in $0$ must be preceded by $1$ ($c_n=b_{n-1}$). Hence $a_n=b_n+c_n=a_{n-1}+a_{n-2}$.
JEE Advanced 2012 · Permutations and Combinations — verified solution by the Vidaara Team.
Log in to post your own answer or join the discussion.
No comments yet — start the discussion.