How to build recuurence relation

#1

Recurrence relation over geeksforgeeks is given as

for (int i = 1; i < n; i++)
{
a[i] = a[i-1] + b[i-1];
b[i] = a[i-1];
}

Can anyone explain me how?

#2

@rssrivastavarohan

Let a[i] be the number of binary strings of length i which end in 0.
let b[i] be the number of such strings which end in 1.

  1. If string ends with 0, we can append either 0 or 1
    so, a[i] = a[i - 1] + b[i - 1]
  2. If string ends with 1, we cannot append another 1, we can append 0 only.
    so, b[i] = a[i - 1]

If you want a simpler relation, you can refer to the video itself. Is the explanation clear?

#3

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.