The question is counting the number $b_{p,q}$ of binary strings with no consecutive $1$’s, with a $0$ at each end. With q 1’s and p 0’s.
How do I prove $b_n = b_{n-1} + b_{n-2}$ is equivalent to saying $b_{p,q}= b_{p-1,q-1}+ b_{p-1,q}$ if $n = p+q$. where $n$ is the number of digits available
Any help would be appreciated!
Here is why $b_{p,q}=b_{p-1,q}+b_{p-1,q-1}$ implies $b_n=b_{n-1}+b_{n-2}$: $$\begin{aligned} b_n &= \sum_{p} b_{p,n-p} \\ &= \sum_{p} b_{p-1,n-p}+b_{p-1,n-p-1} \\ &= \sum_{p} b_{p-1,(n-1)-(p-1)}+\sum_pb_{p-1,(n-2)-(p-1)} \\ &= \sum_{p} b_{p,(n-1)-p}+\sum_pb_{p,(n-2)-p} \\ &= b_{n-1}+b_{n-2} \end{aligned}$$