# Guidelines for Obtaining Recursive Equations?

I'm trying to teach myself some combinatorics, and at the moment, I'm having a hard time coming up with recursive equations. It seems to come naturally to some people, and I'm hoping that my skills may improve if I see one or two examples with some explanation.

For example, let's consider the problem of the probability of getting at least $k$ consecutive heads when tossing a coin $n$ times. The following recursive equation for this problem has been posted here in terms of probabilities: $$P(N,k)=P(N-1,k)+\Big(1-P(N-k-1,k)\Big)\left(\frac{1}{2}\right)^{k+1}$$

This equation seems to be correct when plugging a few numbers in. My questions are:

• What is the mind process for arriving at such equations? Are there any systematic approaches, or at least some helpful tips?
• What if, in general, the probability of obtaining a heads is $p$? Can one still have recursive equation in this case?
-
Probably the most systematic approach is Wilf-Zeilberger algorithm, check out a book called "A=B" –  Alex Feb 12 '13 at 18:55

The logic for that recurrence is that to have a run of $k$ heads out of $N$ flips, you can either have a run out of the first $N-1$ flips and the last one can be anything (the first term on the right) or you can have no run in the first $N-k-1$ flips (the $\Big(1-P(N-k-1,k)\Big)$ term), then a tail (the first factor $\frac 12$), then $k$ heads (the factor $\left(\frac 12 \right)^k$). In general, one way is to carefully enumerate the possibilities.

If the probability of a head were $p$ instead of $\frac 12$ the final $\left(\frac 12 \right)^{k+1}$ would become $(1-p)p^k$, following the logic in the previous paragraph.

-
Thanks a lot for your answer. That perfectly explains the recursion above. With these things it's obvious when someone explains it to you, but it's much harder to come up with it yourself. Hopefully I'll get better with practice. –  MGA Feb 12 '13 at 20:03
@MGA: The hard part is making sure you get all the possibilities once and only once. For this case one might think you could say either the last $k$ are heads (in which case the first $N-k$ can be anything) or they are not, in which case there must be a run in the first $N-1$, so say $P(N,k)=P(N-1,k)+(\frac 12)^k$. This double counts the ones with two runs and those that end in $k+1$ heads. If $N=7,k=3$ we would double count THTHHHH and also HHHTHHH. –  Ross Millikan Feb 12 '13 at 21:00

Most of the time it is to get what you are looking for in terms of "smaller cases". Many times the "smaller cases" come out of fixing an element. A case in point is the number of subsets of size $k$ taken out of $n$ elements. Call this $\binom{n}{k}$ (yes, I'm cheating). Need some boundary conditions here: There is only one way of making a subset of 0 elements or of $n$ elements. It seems logical to also define $\binom{0}{0} = 1$ for symmetry.

Now consider the case of a $k$-element subset made out of $\{1, 2, \ldots, n\}$. Look at $n$, there are two possibilities:

• $n$ is part of the subset; we still need to take $k - 1$ elements out of $\{1, 2, \ldots, n - 1\}$. This can be done in $\binom{n - 1}{k - 1}$ ways.
• $n$ isn't part of the subset; we need to take $k$ elements of $\{1, 2, \ldots, n - 1\}$. This can be done in $\binom{n - 1}{k}$ ways.

Pulling the above together gives: $$\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$$

Or take the number of derangements of $n$ elements (permutations such that the $i$-th element isn't ever $i$, i.e., has no fixed points). Call the number of derangements of $n$ elements $D_n$. Clearly $D_0 = 1$ (when taking 0 elements, none is a fixed point), $D_1 = 0$ (taking 1 element forces that one into position 1), and you can go on. An permutation of $n$ elements has 0, 1, ..., $n$ fixed points, if it has $k$ fixed points the other $n - k$ elements are deranged, in $D_{n - k}$ ways. The $k$ fixed points can be selected in $\binom{n}{k}$ ways. In total there are $n!$ permutations, so $$n! = \sum_{0 \le k \le n} \binom{n}{k} D_{n - k}$$

No, there is (unfortunately) no recipe to find the right decomposition into "smaller cases" (and for derangements there are several other recurrences, check them out). This is just like the searching for the right step when doing proofs by induction. As Pólya says it in his "How to solve it", you have to try lots of examples, and think over what approaches did work, and which ones didn't. This will help in attacking future problems.

-
Thanks a lot for that. I believe that your first recursive equation has a slight mistake. The second term should be multiplied by $k$, because there are $k$ such subsets that do not contain $n$. –  MGA Feb 12 '13 at 20:08
No, it is right. Fix $n$, it is in or not. You take $k - 1$ or $k$ elements out of $n - 1$, and those are as given. –  vonbrand Feb 12 '13 at 20:16
@vongard Thanks, in that case, I still don't quite get it but I'll keep thinking about it until I do. That's why I didn't edit your answer. –  MGA Feb 12 '13 at 20:19
Take, say 3 element sets of $\{1, \ldots, 5\}$ for a small example. Focus on 5, and see how you can construct 3 element sets that include 5 or don't include it. See to express it in terms of subsets of $\{1, \ldots, 4\}$. –  vonbrand Feb 12 '13 at 20:23
Got it! Turns out I was misunderstanding your problem, I was thinking of partitions, which has the exact same recursive equation but with the second term multiplied by $k$. Thanks again for your help. –  MGA Feb 13 '13 at 2:59