Please help me in approaching this problem

#1

Please help me how to approach the problem…

#2

hello @kodivine0
If observed carefully , we can identify that this is a problem for fibonacci series. This is because at the nth place , there are two possibilities.
Possibility 1 : We can choose to place the current character as ‘a’. If so , then it doesn’t matter whether we placed ‘a’ or ‘b’ at the previous position. The total number of ways in this possibility would equal to f(n-1)
Possibility 2 : We can place the current character as ‘b’. However we can only do it if the previous character was not ‘b’ . Hence the total number of ways for this case must be f(n-2)
We add these two possibilities up and obtain the recursive relation
f(n) = f(n-1) + f(n-2)
This is clearly the recursive relation for Fibonacci Series .