Past exam of the mathematics course of the University of Cambridge / 2002 / ia / Paper 2 / 4F / Solution

After $n+1$ independent tosses, an even count arises in exactly two disjoint ways: an even count after $n$ tosses followed by a tail, or an odd count followed by a head. Independence of the last toss from the preceding ones therefore givesSubtracting the fixed point $1/2$ turns this into the linear recurrenceAs zero is even, ${\pi }_0=1$, so the probability isFor $p=1/2$ this is $1/2$ for every $n\ge 1$; for $p=0$ it is always one; for $p=1$ it alternates between one and zero according to the parity of $n$.