Forum de mathématiques - Bibm@th.net

Notons $E_n$ le nombre moyen d'étapes nécessaires pour tirer $0$ pour la première fois si le tirage qu'on s’apprête à faire est parmi $\{0,\dots,n\}$.
Pour $n\geq 1$ alors en conditionnant par rapport au résultat du lancer on trouve $E_n =\frac{1}{n+1}+\sum_{k=1}^n \frac{1}{n+1}(1+E_k)=1+\frac{1}{n+1}\sum_{k=1}^nE_k$. En gros, si $X_n$ est la variable aléatoire qui représente le nombre aléatoires de lancers, alors avec proba $\frac{1}{n+1}$ on tombe sur $0$ auquel cas $X_n=1$, sinon avec proba $\frac{1}{n+1}$ on tombe sur $k\in \{1,\dots,n\}$ auquel cas on aura $X_n=1+X'_k$ où $X'_k$ est indépendante de $X_n$.

On a par exemple $E_1=1+\frac{1}{2}E_1$ donc $E_1=2$.
On a aussi $E_2=1+\frac{1}{3}(2+E_2)$ donc $E_2=\frac{5}{2}$.

De manière générale, on réécrit notre relation de récurrence comme $\frac{n}{n+1}E_n = 1+\frac{1}{n+1}\sum_{k=1}^{n-1}E_k$
En particulier $nE_n-(n+1)=\sum_{k=1}^{n-1}E_k$.
On en déduit que $nE_n-(n+1)=(n-1)E_{n-1}-n+E_{n-1}$ et donc que
$E_n = E_{n-1}+\frac{1}{n}$.
Par télescopage, on trouve $E_n = 1+\sum_{k=1}^{n}\frac{1}{k}$.