Consider the following problem:
You have an urn with a red ball and a blue ball. Every step you draw a ball from the urn, return the ball and add another ball of the same color as the one you drew. After N steps, what is the probability the urn contains k red balls?
By doing a few computations for small $N$ and $k$, it isn't difficult to conjecture that the answer is $\frac{1}{N+1}$, independent of $k$. With this conjecture in mind, it is easy to prove by induction, as $$\frac{1}{a+b-2}\frac{a-1}{a+b-1}+\frac{1}{a+b-2}\frac{b-1}{a+b-1}=\frac{1}{a+b-1}~.$$ However, the particularly nice answer makes me feel there should be a nicer solution. Perhaps there is symmetry to exploit? Or something else lurking? Regardless, does anybody have a particularly nice non-inductive solution to this problem?
Let $B(N)$ be the set of length-$N$ sequences $(b_1,\dots,b_N)$ where each $b_j$ is an integer between $1$ and $j+1$, inclusive. Let $C(N)$ be the set of length-$(N+2)$ sequences $(c_1,\dots,c_{N+2})$ where $c_1 = red$, $c_2=blue$, and $c_j\in\{red,blue\}$ for each $3\le j\le n+2$.
There is a natural function $f\colon B(N)\to C(N)$ given by recursively, for $j=1,2,\dots,N$, defining $c_{j+2}=c_{b_j}$. (In other words, at step $j$ we draw one of the prior $j+1$ balls at random—we choose the $b_j$th ball—and then add a $(j+2)$nd ball of the same color as the $b_j$th ball; we number the balls in the order they appear.) We see that $B(N)$ represents all $(N+1)!$ ways we could have drawn the various numbered balls at the various steps.
There is also a natural bijection $r\colon C(N) \to \mathcal P(\{3,4,\dots,N+2\})$ (the power set of $\{3,4,\dots,N+2\}$) given by $r((c_1,\dots,c_{N+2})) = \{3\le j\le N+2\colon c_j = red\}$.
Claim: let $S\subset \{3,4,\dots,N+2\}$ have cardinality $\ell$. The preimage of $S$ under $r\circ f$ has $\ell!(N-\ell)!$ elements.
Proof: If $s_1$ is the smallest element of $S$, then $b_{s_1}$ must equal $1$; if $s_2$ is the second-smallest element of $S$, then $b_{s_2}$ must equal $1$ or $s_1$; and so on. Similarly, if $t_1$ is the smallest element of $\{3,4,\dots,N+2\}\setminus S$, then $b_{t_1}$ must equal $2$; if $t_2$ is the second-smallest element of $\{3,4,\dots,N+2\}\setminus S$, then $b_{t_2}$ must equal $2$ or $t_1$; and so on. The number of such preimages is exactly $(1\cdot 2\cdots \ell)(1\cdot 2\cdots N-\ell)$.
Now, for any $\ell\in\{0,\dots,N\}$, the number of elements of $B(N)$ that get sent, under $r\circ f$, to a subset of $\{3,4,\dots,N+2\}$ of cardinality $\ell$ is $\binom N\ell$ (the number of such subsets) times $\ell!(N-\ell)!$ (the size of each preimage), or exactly $N!$.
In other words, the probability that a drawing sequence from $B(N)$ gives rise to a sequence of balls containing $k=\ell+1$ red balls is exactly $N!/(N+1)! = 1/(N+1)$.