Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Here is a problem from generatingfunctionology that I'm stuck on:

enter image description here

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.

share|cite|improve this question
This approach will lead to $k$ terms. Are we allowed to use sums? This will reduce it to one term. – Yuval Filmus Mar 11 '11 at 6:28
@Yuval, I'm not sure, this is a screenshot taken directly from the book, but it seems like Wilf (the author) wants to put it in three terms. Any insight is appreciated though. – Dani Hobbes Mar 11 '11 at 6:31
Did you get something out of the answer below? – Did Apr 7 '11 at 8:04
@Didier, Yes, thank you Didier. I hadn't logged in recently, I will accept now. – Dani Hobbes Apr 11 '11 at 20:15
up vote 7 down vote accepted

Assume $m$ and $n$ are large, say larger than $k$. If you continue your what-is-the-end-of-the-string argument, you will get $f(n,m,k)$ as the sum of $f(n-i,m-i+1,k)$ from $i=1$ to $i=k$, each of these terms counting the strings ending by $01^{i-1}$. Now, this sum has $k$ terms and you want only three.

Compare the $k$ terms sums for $f(n,m,k)$ and for $f(n-1,m-1,k)$.

The same terms appear in both sums with two exceptions: the first term of $f(n,m,k)$ is $f(n-1,m,k)$, which is not in $f(n-1,m-1,k)$, and the last term of $f(n-1,m-1,k)$ is $f(n-1-k,m-k,k)$, which is not in $f(n,m,k)$. Of course this reflects a combinatorial fact, which I let you explicit.

Hence, at least for large enough $n$ and $m$, $$ f(n,m,k)=f(n-1,m-1,k)+f(n-1,m,k)-f(n-1-k,m-k,k). $$

share|cite|improve this answer
Thank you Didier. However, I'm still hoping to solve it the way the book presents it, in order to address parts (b) and (c) later. – Dani Hobbes Mar 13 '11 at 1:26
@Hobbie I fail to see why you think this is not the way the book suggests, especially in view of (b) and (c). – Did Mar 13 '11 at 8:25
I suppose I think it's not the way the book suggests, since part (a) says the recurrence should have $f(n,m,k)$ on the left, not $f(n,m)$, and then uses $f(n,m,k)$ in the summation of part (b), and then asks for an explicit formula for $f(n,m,k)$ in part (c). – Dani Hobbes Mar 13 '11 at 22:17
@Hobbit Your answer makes no sense. Did you notice that $k$ is fixed once and for all in all the exercise (which is why I said in the first sentence of my post that I will omit it)? I put $k$ back in my post. – Did Mar 14 '11 at 6:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.