A full binary tree has every edge colored black or white randomly. What is the probability of having a white path from the root to some leaf? 
A full binary tree has every edge colored black or white randomly.
What is the probability of having a white path from the root to some
leaf?
A) $\Theta(1)$
B) $\Theta(\frac{1}{n})$
C)  $e^{-\Theta(n)}$
D) $(\log n)^{-\Theta(1)}$

Every edge has a 0.5 chance of being white and 0.5 chance of being black. The tree is of depth $n$ so therefore it has $2^n$ leafs with distinct paths to them and every path is of length $n$.
I'm not sure how to solve this question. I'm really not sure where to start. The odds of a random path being white is $(\frac{1}{2})^n$ and there are $2^n$ different paths to the leafs, but it's not true that $P=2^n(\frac{1}{2})^n $ Because that just equals 1.
 A: Hint: start from the top and work down. Right from the start, you have a 25% chance of failing (both edges from the root are black).  Apply this r
recursively. 

To expand a bit on this, separate into four different cases depending on our two child edges, BB (black/black), BW, WB and WW, each having probability $\frac{1}{4}$:
\begin{align}
p(n) &= \frac{1}{4}\cdot 0 \quad &\text{(BB)}\\
     &+\frac{1}{4}\cdot p(n-1) &\text{(BW)}\\
     &+\frac{1}{4}\cdot p(n-1) &\text{(WB)}\\
     &+\frac{1}{4}\cdot (1 - (1 - p(n-1))^2) &\text{(BB)}\\
\end{align}
Note that for the last case we use $1$ minus the chance that both fail, which gives the chance that at least one succeeds. Simplifying this we get:
$$p(n) = p(n-1) - \frac{1}{4}p(n-1)^2$$
$$p(n) = p(n-1)(1 - \frac{1}{4}p(n-1))$$
Also keep in mind that $p(1) = 1$, because the path from a node to itself always exists.
Solving these types of recurrences isn't easy, see Did's answer to go from here (or better, attempt it yourself). 
A: The recursion

$$p(n)=p(n-1)-\frac14p(n)^2$$ 

is a simple consequence of the one-level decomposition of the tree. To deduce some asymptotics of $p(n)$, one first notes that every $p(n)$ is in $(0,1]$ hence $p(n)$ is a nondecreasing function of $p(n-1)$. 
Now, one is ready to show that, for every $n\geqslant0$, 

$$\frac3{n+3}\leqslant p(n)\leqslant\frac4{n+4}\tag{$\ast$}$$

The $n=0$ case of $(\ast)$ follows from the value $p(0)=1$. (If one is uncomfortable with the (perfectly legit) notion that $p(0)$ exists and that $p(0)=1$, one can instead check $(\ast)$ for $p(1)=\frac34$). 
If $(\ast)$ holds for some $n\geqslant0$, $$\frac3{n+3}-\frac14\left(\frac3{n+3}\right)^2\leqslant p(n+1)\leqslant\frac4{n+4}-\frac14\left(\frac4{n+4}\right)^2$$
hence, to deduce that $(\ast)$ holds for $n+1$ as well, it suffices to check that, for every $n\geqslant0$, $$\frac3{n+4}\leqslant\frac3{n+3}-\frac14\left(\frac3{n+3}\right)^2\tag{1}$$ and that, for every $n\geqslant0$, $$\frac4{n+4}-\frac14\left(\frac4{n+4}\right)^2\leqslant\frac4{n+5}\tag{2}$$
It happens that $(1)$ and $(2)$ are both direct hence all this proves that $(\ast)$ holds for every $n\geqslant0$. In particular,

$$p(n)=\Theta\left(\frac1n\right)$$

A: Let $p(n)$ be the probability of a tree with depth n having a white path from the root to a leaf. Starting from the root and working down, notice that there are 3 possibilities for the first level:


*

*Both edges are white (probability $.25$), reducing our problem to two independent cases of trees with depth $n-1$

*Both edges are black (probability $.25$), in which case we've already lost

*One edge is black, one edge is white (probability $.5$), in which case we simply have a tree with depth $n-1$ 


Combining these three mutually exclusive cases by the law of total probability yields:
\begin{align*}
p(n) &= .25(1 - (1 - p(n-1))^2) + .5p(n-1) \\
     &= -\frac{1}{4}p(n-1)^2 + p(n-1)
\end{align*}
Can you solve that recurrence and get a closed form? Not to inherently imply the existence of a closed form. I'm simply stating that if you can find such a closed form, that would allow you to finish the problem.
