Writing a Recursive Sequence and finding out limit by a "weird" property I apologize for lacking of a better title and for potencial math language mistakes as I'm not an english native so there's some terms I might miss. I found out a note of my college that had the following written on:
Calculate $\lim(x_n)$ if $$x_n=\frac{n}{2^{n+1}}\sum_{i=1}^{n}\frac{2^i}{i}$$
Then their resolution follows as:
This sequence can be defined by recursion as
$$x_{n+1}= \frac{n+1}{2n}.\underbrace{\frac{n}{2^{n+1}}\sum_{i=1}^{n}\frac{2^i}{i}}_{x_n} + \frac{n+1}{2^{n+2}}\frac{2^{n+1}}{n+1} = $$
$$\frac{n+1}{2n}x_n + \frac{1}{2} = x_{n+1}$$
I really don't understand how they defined the recursive sequence, I tried to calculate $x_{n+1}$ and had a different result than the solution everytime I tried (if I even did it correctly). The next step is perhaps the most confuse to me, as they said:
$\frac{n+1}{2n} \to \frac{1}{2}\hspace{1.5mm}\text{(obvious to me)}$ and as stated in a theorem we studied before (I really don't recognize this theorem and can't search for it) $x_n$ has a limit and it is given by $$\frac{\frac{1}{2}}{1 - \frac{1}{2}} = 1$$
Besides not getting how they defined the recursive sequence I believe I'm not aware of the theorem they stated as well (even though the outcome looks like the sum of a geometric series of ratio $\frac{1}{2}$ starting on the first term) so I would really appreciate it if someone could help me figuring out both things.
Thank you so much for your attention.
 A: Perhaps it will be clearer if I include a few more steps:
$$\begin{align*}
x_{n+1}&\overset{(1)}=\frac{n+1}{2^{n+2}}\sum_{i=1}^{n+1}\frac{2^i}i\\
&\overset{(2)}=\left(\frac{n+1}{2n}\cdot\frac{n}{2^{n+1}}\right)\left(\sum_{i=1}^n\frac{2^i}i+\frac{2^{n+1}}{n+1}\right)\\
&\overset{(3)}=\frac{n+1}{2n}\color{red}{\left(\frac{n}{2^{n+1}}\sum_{i=1}^n\frac{2^i}i\right)}+\left(\frac{n+1}{2n}\cdot\frac{n}{2^{n+1}}\cdot\frac{2^{n+1}}{n+1}\right)\\
&\overset{(4)}=\frac{n+1}{2n}x_n+\frac12
\end{align*}$$
Step $(1)$ is just the definition of $x_{n+1}$. Step $(2)$ is rewriting the coefficient $\frac{n+1}{2^{n+2}}$ in what will prove to be a more useful form and splitting off the $i=n+1$ term of the summation. Step $(3)$ is just multiplying out and emphasizing the red part as a single unit. And step $(4)$ is identifying that unit as $x_n$ and simplifying the last term.
It follows that if $\langle x_n:n\in\Bbb Z^+\rangle$ converges to some limit $x$, we must have
$$\begin{align*}
x&=\lim_{n\to\infty}x_{n+1}\\
&=\frac12+\lim_{n\to\infty}\frac{n+1}{2n}x_n\\
&=\frac12+\left(\lim_{n\to\infty}\frac{n+1}{2n}\right)\lim_{n\to\infty}x_n\\
&=\frac12+\frac{x}2
\end{align*}$$
and hence $x=1$. Thus, we have only to make sure that the sequence actually does converge. I don’t know what theorem was intended, but here is a (somewhat brute force) argument to show that the sequence converges.
By direct calculation $x_3=\frac54$. An easy induction on $n$ applied to the recurrence
$$x_{n+1}=\frac{n+1}{2n}x_n+\frac12$$
shows that $x_n>1$ for all $n\ge 3$: if $x_n>1$, then $\frac{n+1}{2n}x_n>\frac12$, and $x_{n+1}>1$.
Note that $x_n-x_{n+1}=\frac{n-1}{2n}x_n-\frac12$ is non-negative if and only $x_n\ge\frac{n}{n-1}$. By direct calculation $x_4=\frac43=\frac4{4-1}$. Suppose that $x_n\ge\frac{n}{n-1}$ for some $n\ge 4$. Then
$$\begin{align*}
x_{n+1}&=\frac{n+1}{2n}x_n+\frac12\\
&\ge\frac{n+1}{2n}\cdot\frac{n}{n-1}+\frac12\\
&=\frac{n+1}{2(n-1)}+\frac{n-1}{2(n-1)}\\
&=\frac{2n}{2(n-1)}\\
&=\frac{n}{n-1}\\
&>\frac{n+1}n\,,
\end{align*}$$
so by induction $x_n\ge\frac{n}{n-1}$ for all $n\ge 4$ (and in fact the strict inequality at the last step means that $x_n>\frac{n}{n-1}$ for all $n\ge 5$). It follows that $x_n-x_{n+1}\ge 0$ for all $n\ge 4$ (and in fact that $x_n-x_{n+1}>0$ for $n\ge 5$), so the sequence $\langle x_n:n\ge 4\rangle$ is decreasing and bounded below and therefore must converge.
