Here is a problem from generatingfunctionology that I'm stuck on:
I'm trying to get started on part (a). I broke the string up like this. If the last digit is $0$, the number of possible strings is then $f(n-1,m,k)$. If the last digit is $1$, there are two subcases. If the $n-1^{th}$ digit is $0$, then we can cut them both off and the number of strings is $f(n-2,m-1,k)$. However, if the $n-1^{th}$ digit is $1$, then I don't know what to say, since even if I cut both last $1$s off, I can't have the last $k-2$ numbers of my $n-2$ long string be $1$s, but it's entirely possible that I could have $k-2$ $1$s earlier in the string. So I have something like: $ f(n,m,k)=f(n-1,m,k)+f(n-2,m-1,k)+??? $ and I don't know what third term to put there. What is the third term? Thanks.
If it's not trouble, I may ask questions on parts (b) and (c) when I get there.