For n ≥ 0, let us toss a coin 2n times.
(a) If an is the number of sequences of 2n tosses where n heads and n tails occur, find an in terms of n.
(b) Find constants r, s, and t so that (r + sx)t = f(x) = ∑∞n=0 anxn.
(c) Let bn denote the number of sequences of 2n tosses where the numbers of heads and tails are equal for the first time only after all In tosses have been made. (For example, if n = 3, then HHHTTT and HHTHTT are counted in bn, but HTHHTT and HHTTHT are not.)
Define b0 = 0 and show that for all n > 1,
an = a0bn + a1bn-1 + ∙ ∙ ∙ + an-1b| + anb0.
(d) Let g (x) = ∑∞n=0 bnxn. Show that g (x) = 1 - 1 / f(x), and then solve for bn,n ≥ 1.