Finding expected value with recursion We'll start off with an example of a question of finding expected value.
What is the expected number of tries to get $6$ when rolling dice?
$$
\mathbb{E}[x] =1/6*1 + 5/6 * (1+\mathbb{E}[x]) \implies \mathbb{E}(x)=6
$$
I understand the intuition, there is a 1/6 probability of getting 6 in one roll and 5/6 of not getting 6, so we roll again and add 1 to the counter since we have done one roll. I wonder what is the formal proof of such method?
 A: $\newcommand{\E}{\operatorname{E}}$Google the term "law of total expectation".
The conditional expected value of a random variable $X$ given the event that another random variable (capital) $Y$ is equal to a particular number (lower-case) $y$ is
$$
\E(X\mid Y=y).
$$
That depends on what number $y$ is: it's a function of $y$.  So call it $g(y)$.  We have
$$
\E(X\mid Y=y)=g(y).
$$
Then we can define
$$
\E(X\mid Y) = g(Y),
$$
which is a random variable in its own right.  The conditional expected value of a random variable $X$ given the value of a random variable $Y$ is another random variable that depends on $Y$.
The law of total expectation says that the expected value of that random variable is the same as the expected value of $X$:
$$
\E(\E(X\mid Y)) = \E(X).
$$
So let $X$ be the number of trials needed to get "$6$" when you throw the die.
Let $Y$ be the number of "$6$"s that appear on the first trial, so $Y$ is either $0$ or $1$.
Then
\begin{align}
\E(X\mid Y=1) & = 1, \\[6pt]
\E(X\mid Y=0) & = \E(X)+1.
\end{align}
In other words, given that you got a "$6$" on the first trial, the conditional expected value of $X$ is $1$, and given that you failed to get a "$6$" on the first trial, the conditional expected value of $X$ is $1$ more than it would otherwise have been.
Now notice that
\begin{align}
\E(X\mid Y) = \begin{cases} 1 & \text{with probability }1/6, \\[6pt]
1+\E(X) & \text{with probability }5/6. \end{cases}
\end{align}
So
$$
\E(X) = \E(\E(X\mid Y)) = \frac16\cdot1 + \frac56\cdot(1+\E(X)).
$$
So you have an algebraic equation
$$
w = \frac16\cdot1+\frac56\cdot(1+w).
$$
A: The process is memoryless so $\Pr(X=i\mid X \gt n) = \Pr(X=i-n)$.
So $$E[X] = \sum_{i=1}^\infty i \Pr(X=i) $$ $$=  \Pr(X=1) + \sum_{i=2}^\infty i \Pr(X=i\mid X \gt 1) \Pr(X \gt 1) $$ $$=  \Pr(X=1) + \Pr(X \gt 1) \sum_{j=1}^\infty (1+j) \Pr(X=j) $$ $$=  \Pr(X=1) + \Pr(X \gt 1) \sum_{j=1}^\infty \Pr(X=j)+ \Pr(X \gt 1) \sum_{j=1}^\infty j \Pr(X=j) $$ $$=  \Pr(X=1) + \Pr(X \gt 1)(1+ E[X])$$ 
though this is easily simplified to $E[X]= 1 + \Pr(X \gt 1) E[X]$ or $E[X]= 1 / \Pr(X = 1)$. 
