When flipping a coin 12 times, what is the probability that, at some point after the first flip, the number of heads equals the number of tails? The solution says to let $F_{n,k}$ be the number of ways to flip the coin $n$ times such that the positive difference between the number of heads and the number of tails is equal to $k$. Then we should find a recurrence $F_{n,k} = F_{n-1,k-1} + F_{n-1,k+1}$. I am not sure 1) how to derive this recurrence relation and 2) how we can use this to solve this problem. The correct answer is suppose to be  $\boxed{\dfrac{793}{1024}}$. Any help would be appreciated. 
 A: This is an incomplete answer, but was too long for a comment.  At any rate, it explains part (1) of your question, namely

How do we derive the recurrence relation?

In a slight variation of the original notation, let $F_{n,k}$ denote the number of ways of obtaining $k$ as the number of heads minus the number tails after $n$ tosses.  Note that $F_{n,k}$ can take on integer values between $-n$ and $n$ (inclusive).
If we have already flipped the coin $n-1$ times, then there are only two possible ways that we can get the difference between heads and tails to be $k$ on the $n$-th toss:

*

*After the $(n-1)$-st toss, we had $k-1$ more heads than tails, then got heads on the $n$-th toss.  There are $F_{n-1,k-1}$ ways for this to happen.

*After the $(n-1)$-st toss, we had $k+1$ more heads than tails, then got tails on the $n$-th toss.  There are $F_{n-1,k+1}$ ways for this to happen.

This gives the recurrence relation
$$ F_{n,k} = F_{n-1,k-1} + F_{n-1,k+1}.$$
Note that this is slightly different than the way you originally phrased the problem.  Here, we are counting the signed difference between the number heads and tails, not the absolute difference.

How do we use the recurrence relation to determine the probability of having an equal number of heads and tails at some point after the first toss?

We can now use this recurrence relation to count the different ways of obtaining a difference of $k$.  We end of with something reminiscent of Pascal's triangle:
\begin{matrix}
& \dotso & -4 & -3 & -2 & -1 & 0 & 1 & 2 & 3 & 4 & \dotso  && \leftarrow\text{difference}\\\hline
\text{1 toss} &&&&& 1 & 0 & 1 \\
\text{2 tosses} &&&& 1 & 0 & 2 & 0 & 1 \\
\text{3 tosses} &&& 1 & 0 & 3 & 0 & 3 & 0 & 1 \\
\text{4 tosses} && 1 & 0 & 4 & 0 & 6 & 0 & 4 & 0 & 1 \\
\end{matrix}
Indeed, this is exactly Pascal's triangle, with a bunch of zeroes added in.  It might be nice to prove that
$$ F_{n,k} = \begin{cases}
0 & \text{if $n$ and $k$ have different parity, and} \\
\displaystyle\binom{n}{\frac{1}{2}(n+k)} & \text{if $n$ and $k$ have the same parity.} \\
\end{cases}
$$
Note that we could have come to the same conclusion by noting that the number of heads after $n$ tosses is binomially distributed, from which we could deduce the formula above.
At this point, we have a formula for computing $F_{n,k}$ for any $n$ and $k$, which we can use to compute probabilities.  Unfortunately, there is quite a bit of redundancy, so the computation is a little tedious.
A: Thanks for the posts! After understanding how the recursion is formed I managed to solve the problem by using complementary counting. Since the "same number" of flips for heads and tails can occur anywhere it is difficult to use a constructive counting method with PIE. Rather, let all $F_{n,o} = 0$ for all $n$ and proceed with building up the recursion. We can then add up all $F_{12,k}$ where k is an even not equal to zero to find the number of ways to flip 12 coins without having the same number of heads and tails anywhere. Subtracting this from $2^{12}$ and dividing by $2^{12}$ yeilds the correct answer. The recursion is not too bad as we only need to consider even k for an even n and odd k for an odd n. Also building the recursion from bottom-up is considerably faster then top-down.
