Counting Binary Strings

#1

Sir I am unable to think of the base case in this problem. Please help.

#2

hi @harshit_7547 did you understand the recursive relation? If yes please write it down here

#3

Yes mam. In recursive relation we have to options , we can put 0 or 1, but when we will put 0 then we have got no restrictions so f(n-1) for this to proceed but if we put 1 here then at next place we have to put 0 so we have f(n-2) and then sum of these two will give me recursive relation

#4

Mam I think on the case n<0 we will return 1 in this question and on n==0 too

#5

@harshit_7547
you have understood the recursive case pretty well
f(n) = f(n-1) + f(n-2)

for the base case
if n <= 0
you cannot make any strings, so you can say f(n) = 0

if n==1
possible strings: 0, 1
so f(1) = 2

if n==2
possible strings: 00, 10, 01
so f(2) = 3

#6

Ok mam, Got it, TYSM!

1 Like
#7

@harshit_7547 dont forget to mark your doubt as resolved!

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like