I’ll leave (a) to you: with the suggestion to do it by induction on $n$, it really is pretty easy, especially after you’ve seen an inductive proof of (b).
Problem (b) can also be done by induction. Let $p(n,k)$ be the probability that Ann has $k$ dollars after $n$ plays. In order to have $k$ dollars after $n$ plays, she must either have had $k$ dollars after $n-1$ plays and lost on the $n$-th play, or have had $k-1$ dollars after $n-1$ plays and won on the $n$-th play. If she has $k$ dollars after $n-1$ plays, her probability of losing on the $n$-th play is $\frac{k}{n+1}$. If she has $k-1$ dollars after $n-1$ plays, Bob has $n+2-k$ dollars, so her probability of winning on the $n$-th play is $\frac{n+2-k}{n+1}$. It follows that $\begin{align*} p(n,k) &= p(n-1,k)\frac{k}{n+1}+p(n-1,k-1)\frac{n+2-k}{n+1}\\ &= \frac1{n+1}\left(kp(n-1,k)+(n+2-k)p(n-1,k-1)\right) \end{align*}$ for $1\le k\le n$. The initial conditions for the recurrence are clearly $p(0,1)=1$ and $p(n,0)=0$ for all $n\ge 0$.
Now consider the numbers $A(n,k)$. It’s easy to see that $A(n,1)=A(n,n)=1$ for all $n>0$. Now consider $A(n+1,k)$. A permutation of $[n+1]$ with $k$ runs can be obtained in two ways from a permutation of $[n]$.
- We can start with a permutation of $[n]$ that has $k$ runs and insert $n+1$ at the end of one of these runs; each of the $A(n,k)$ permutations of $[n]$ with $k$ runs gives rise in this way to $k$ permutations of $[n+1]$ with $k$ runs.
- We can start with a permutation of $[n]$ that has $k-1$ runs and insert $n+1$ in any of the $n+1-(k-1)=n+2-k$ positions that are not at the end of a run; each of the $A(n,k-1)$ permutations of $[n-1]$ with $k-1$ runs gives rise in this way to $n+2-k$ permutations of $[n+1]$ with $k$ runs.
It follows that $A(n+1,k)=kA(n,k)+(n+2-k)A(n,k-1)\;.$ Thus, if $p(n-1,k)=\frac{A(n,k)}{n!}$ and $p(n-1,k-1)=\frac{A(n,k-1)}{n!}$, then $\begin{align*} p(n,k) &= \frac1{n+1}\left(k\frac{A(n,k)}{n!}+(n+2-k)\frac{A(n,k-1)}{n!}\right)\\ &= \frac{A(n+1,k)}{(n+1)!}, \end{align*}$ and all that remains is to check the boundary conditions.