I want to find the limit of a recursive sequence given below: $$p_{n+1}=\frac{p_n^2+k}{2p_n}, \ \ \forall k \in \mathbb{R}$$ How would I go about it? I know this converges because it is the NR approximation for square roots. Thus, I ask too, if whether the limit of that relation above will give me the square root of $k$.
If you could write it in the most elementary of terms and with as much intuition as possible, that would be appreciated.
On
We can show that $\lim_{n\to\infty}p_n=\sqrt{k}$. First, by the AM-GM inequality, we can see that $$p_{n+1}=\frac{p_n^2+k}{2p_n} \ge \sqrt{k}$$ Thus, $p_{n}-\sqrt{k} \ge 0$ for all $n$. Now,
$$\frac{p_{n+1}-\sqrt{k}}{p_{n}-\sqrt{k}}=\frac{\frac{p_n}{2}+\frac{k}{2p_n}-\sqrt{k}}{p_{n}-\sqrt{k}}$$ $$=\frac{1}{2}\frac{\left( \sqrt{p_n} - \frac{\sqrt{k}}{\sqrt{p_n}}\right)^2}{p_{n}-\sqrt{k}}=\frac{1}{2}\frac{p_n-\sqrt{k}}{p_n}$$ $$<\frac{1}{2}$$ Thus, $p_n-\sqrt{k}<\frac{1}{2^n}(p_0-\sqrt{k})$ which is enough to show that $\lim_{n\to\infty} (p_n-\sqrt{k})=0$
If you’ve proven the limit $L$ exists you can let $n\to \infty$ so the recurrence becomes $$L=\frac{L^2+k}{2L}$$ So $L^2=k$. Provided $p_n>0$ and $k>0$ you can conclude $L=\sqrt{k}$