At time $0$, an urn contains $1$ black ball and $1$ white ball. At each time $1,2,3,...,$ a ball is chosen at random from the urn and is replaced together with a new ball of the same colour. Just after time $n$, there are therefore $n+2$ balls in the urn, of which $B_n+1$ are black, where $B_n$ is the number of black balls chosen by time $n$. Let $M_n = \frac{B_n + 1}{(n + 2)}$, the proportion of black balls in the urn just after time $n$. Prove that (relative to a natural filtration which you should specify) $M$ is a martingale.
There are several ways of solving the problem. One proof starts off by letting $\mathcal{F}_n=\sigma(B_1,...,B_n)$ and then stating $$E[M_n|\mathcal{F}_{n-1}]=P(B_n=B_{n-1})\frac{B_{n-1}+1}{n+2}+P(B_n=B_{n-1}+1)\frac{B_{n-1}+2}{n+2}$$ Intuitively speaking, I agree completely with the equation. It reminds of the basic definition of conditional expectation for discrete rv $X$ given $Y=y$: $$E(X|Y=y)=\sum_xx\cdot P(x|y)$$ How can one prove the equation rigorously? There are similar problems like De Moivre's martingale (https://en.wikipedia.org/wiki/Martingale_(probability_theory)) which make use of the same property of conditional expectation to state: $$E(Y_{n+1}|X_1,...,X_n)=p\left(\frac{q}{p}\right)^{X_n+1}q\left(\frac{q}{p}\right)^{X_n-1}$$ from which it is easy to then show that $(Y_n)_{n\in\mathbb{N}}$ is a martingale. What is the general formula that I am missing which applies to both of these problems?
We set $\mathscr{F}_k:=\sigma(B_u,u\leq k)$. The differences $(B_n-B_{n-1})_{n \in \mathbb{N}}$ can only take the values $\{0,1\}$. We have, for $f$ measurable and under the integrability condition $E[|f(B_n-B_{n-1})|]<\infty$ $$\begin{aligned}E[f(B_n-B_{n-1})|\mathscr{F}_{n-1}]&=\sum_{k \in \{0,1\}}f(k)P(B_n-B_{n-1}=k|\mathscr{F}_{n-1}) \end{aligned}$$ If we define $f(x)=\frac{x+1}{n+2}$ we obtain $$\begin{aligned}E[f(B_n-B_{n-1})|\mathscr{F}_{n-1}]&=\underbrace{P(B_n-B_{n-1}=0|\mathscr{F}_{n-1})}_{:=p_{0,n-1}}\frac{1}{n+2}+\underbrace{P(B_n-B_{n-1}=1|\mathscr{F}_{n-1})}_{:=p_{1,n-1}}\frac{2}{n+2}\end{aligned}$$ By rearranging the terms $$\begin{aligned}E\bigg[\frac{B_n+1}{n+2}\bigg|\mathscr{F}_{n-1}\bigg]&=\frac{B_{n-1}}{n+2}+p_{0,n-1}\frac{1}{n+2}+p_{1,n-1}\frac{2}{n+2}=\\ &=p_{0,n-1}\frac{B_{n-1}+1}{n+2}+p_{1,n-1}\frac{B_{n-1}+2}{n+2}\end{aligned}$$
Similarly, in the other problem we obtain for $\mathscr{G}_k:=\sigma(X_u,u\leq k)$
$$\begin{aligned}E[Y_nY_{n-1}^{-1}|\mathscr{G}_{n-1}]&=E\bigg[\bigg(\frac{q}{p}\bigg)^{X_n-X_{n-1}}\bigg|\mathscr{G}_{n-1}\bigg]=\\ &=\sum_{k \in \{-1,1\}}\bigg(\frac{q}{p}\bigg)^kP(X_n-X_{n-1}=k|\mathscr{G}_{n-1})=\\ &=\bigg(\frac{q}{p}\bigg)^{-1}q+\bigg(\frac{q}{p}\bigg)p\end{aligned}$$ and so $$E[Y_n|\mathscr{G}_{n-1}]=Y_{n-1}\bigg(\frac{q}{p}\bigg)^{-1}q+Y_{n-1}\bigg(\frac{q}{p}\bigg)p$$