Sunday, June 24, 2018

limits - What is the real answer for this geometric series?




I recently read a book about Data structures, int that book I found this equation under topic, "the average number of probes for an unsuccessful search":




enter image description here




but when I was trying to prove this I found another expression,
here is how I tried:




enter image description here



enter image description here



enter image description here



enter image description here



enter image description here




enter image description here



enter image description here



So my proof led me to this equation



enter image description here



So what did I do wrong, I can't find any error above?




Or Am I right?


Answer



Your answer is right. $\lambda =0$ should give both the right hand side and left side to be zero, which is clearly not the case in the formula given in the text.



Another way to obtain the same answer is as follows. We have
\begin{align}
\sum_{k=0}^{\infty} \lambda^k = \dfrac1{1-\lambda} \,\,\, \forall \left \vert \lambda \right \vert < 1
\end{align}
Differentiating the above we obtain
\begin{align}

\sum_{k=0}^{\infty} k\lambda^{k-1} = \dfrac1{(1-\lambda)^2} \,\,\, \forall \left \vert \lambda \right \vert < 1
\end{align}
Multiplying by $\lambda$, we obtain
\begin{align}
\sum_{k=0}^{\infty} k\lambda^{k} = \dfrac{\lambda}{(1-\lambda)^2} \,\,\, \forall \left \vert \lambda \right \vert < 1
\end{align}


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...