Solving recurrence using telescopic sums

597 Views Asked by At

Use the method of telescoping sums to solve the recurrence $nx_n = (n−2)x_{n−1} +1, n\geqq1$, where $x_0=0$.

I did this using the method of inspection. In that I found that $x_n=\frac{1}{2}$ for all $n\geqq2$. But how can this be done using telescopic sums?

1

There are 1 best solutions below

0
On BEST ANSWER

By the telescopic summation we obtain: $$n=\sum_{k=1}^n\left(kx_k-(k-2)x_{k-1}\right)=\sum_{k=1}^n\left(kx_k-(k-1)x_{k-1}+x_{k-1}\right)=nx_n+\sum_{k=1}^nx_{k-1},$$ which gives $$x_n=1-\frac{\sum\limits_{k=0}^{n-1}x_k}{n}.$$ Now, easy to see that $x_2=\frac{1}{2}$ and let $x_k=\frac{1}{2}$ for all $2\leq k\leq n.$

Thus, $$x_{n+1}=1-\frac{\sum\limits_{k=0}^{n}x_k}{n+1}=1-\frac{n(1-x_n)+\frac{1}{2}}{n+1}=1-\frac{n\cdot\frac{1}{2}+\frac{1}{2}}{n+1}=\frac{1}{2}$$ and we are done!