Recurrence Relation

Question

The recurrence relation for the number of n-digit quaternary sequences that have an even number of zeros (quaternary sequences use only 0,1,2,3 for digits) is-

(A) a_n = a_n-1 + 4^n-1

(B) a_n = 3a_n-1 + 4^n-1

(C) a_n = 2a_n-1 + 4^n-1

(D) a_n = a_n-1 + 4^n-2

Answer 1

Ok, C is correct , you can check by calulcating some values.

f[1] = 3 ,     { 1  , 2 , 3  }

f[2] = 10    , { 00 , 11 , 12, 13 , 21 , 22 , 23 , 31 ,32 , 33 }

f[3] =  36  

No zero total number =  3 ^ 3 =  27

Two zero   =  9  {   100 , 200 , 300 , 010 , 020 , 030 , 001, 002, 003 }  

Hence C is correct  :   f(n) = 2 * f(n-1) + 4 ^ (n - 1 )   

Also F(n)  =   C(n,0) * 3^n   + C(n,2) * 3^(n - 2 )   +  C(n,4) * 3 ^ ( n - 4 )   + .......      C(n,r)  * 3 ^(n - r )    

Because , either you used 0 times 0 , 2 times 0  , 4 times 0     .....

Answer 2

a_n = 2a_n-1 + 4^n-1

Case 1: nth place occupied by 1/2/3, then no of solutions = 3*a_n-1

Case 2: nth place occupied by 0, then the string a[1:n-1] should have odd number of 0s.

We know a_n-1 = string of length n-1 with even 0s.

Total string of length n-1 = 4^n-1

Thus, string of length n-1 with odd number of 0s = 4^n-1 - a_n-1

_=> a_n = 3*a_{n-1 +} 4^n-1 - a_n-1 

=> a_n = 2a_n-1 + 4^n-1