Consider the case where both A and B throws N coins, let the probability that A has more heads than B be P(A), the probability that A and B has the same number of heads be P(T), the probability that B has exactly 1 more head than A be P(B1), and B has 2 or more heads than A be P(B2), then P(A) = P(B1) + P(B2).

For the case where A throws N+1 coins, we can treat it as if both A and B throws N coins first, then A throws an extra one. Therefore

P'(A) = P(A) + P(T) / 2, P'(B) = P(B2) + P(B1) / 2

Obviously, P'(A) > P'(B)