I pulled this up from the MIT Open CourseWare page under their Problem Solving class. I think they use problems of this caliber to prepare for the Putnam exam.
I wonder if we as a class could take on this one...
3. An unfair coin (probability p of showing heads) is tossed n times. What
is the probability that the number of heads will be even?
That's a great idea. First, try it for specific values of n. If n=1, then the number of heads is even if it's 0, so P(even) = 1-p. If n=2, you could have 0 or 2 heads, so P(even) = (1-p)^2 +p^2 = 1-2p. Obviously there's going to be some kind of binomial identity, but what?
OK, I now know two ways to solve this. The first way was along the lines you described in the break to me, Sam. It makes more sense than I originally thought, and with your Discrete Math knowhow you might be able to solve it.
There's also a clever way, which I admit I didn't figure out until I solved it the other way.