Pascal's Triangle explains it. Let's say two people toss two coins each. Each person has a 5/16 probability of more heads, and the probability of the same amount of heads is 6/16. This matches the row of Pascal's Triangle that adds up to 16. The row is 1-4-6-4-1. 1+4 = 5, 6 = 6, and 4+1 = 5. With the same amount of tosses, A had P = 5/16 of more heads, in which case an another toss is irrelevant. A has P = 5/16 of having fewer heads, in which case A can tie B but not exceed B with one more toss. In the P = 6/16 that the amount of heads are equal, P = (6/16)(1/2) = 3/16 that A will go from tied with B to one more than B with one more toss. 5/16 = 3/16 = 1/2. The rows of comparing probabilities are all rows with an odd amount of numbers and one middle number. As romsek posted, the exponent when two people toss the same amount of coins is 2n, so we never have to work with rows that sum to 2 to an odd power like 1-3-3-1. The short statement is that the sum of all numbers to the left of the middle number plus half of the middle number = the sum of all numbers to the right of the middle number plus half of the middle number = 1/2.

That answer is not dependent on the amount of coins. I want to know whether the probability of having more heads from two more tosses depends on the amount of tosses. It does. The sequence is:

P (A gets more heads from two tosses than B from zero) = 3/4

P (A gets more heads from three tosses than B from one) = 3/4 - 1/16 = 11/16

P (A gets more heads from four tosses than B from two) = 3/4 - 1/16 - 1/32 = 21/32

Each term is the previous term minus half of the last part of the previous part. Can somebody write that in Sigma notation?