retagged by
500 views
0 votes
0 votes
an is a n-digit number of 0's and 1's with no consecutive 0's i.e., without the occurrence of '00'. For example, a8 =10111011. Construct a recurrence relation for an(a0=1).
retagged by

2 Answers

1 votes
1 votes
Here The strings of length one (a1) and which do not have two consecutive Zeros

  0,1

The strings of length two (a2) and which do not have two consecutive Zeros,

01,10,11

The strings of length three (a3) and which do not have two consecutive Zeros,

010 ,011, 101, 110, 111

The strings of length four (a4) and which do not have two consecutive Zeros,

0101 , 0110 , 0111 , 1010 , 1011, 1101, 1110, 1111

Clearlly here a1=2
              a2=3
              a3=a1+a2=5
              a4=a3+a2=8

So recurance relation a(n)=a(n-1)+a(n-2) for n>=3

Related questions

66 votes
66 votes
10 answers
3
Sandeep Singh asked Feb 12, 2016
28,219 views
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n-1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.