Guidelines for Obtaining Recursive Equations?

Question

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?

Answer 1

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.

Answer 2

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.