1

I am having trouble to calculate $$\sum_{i=1}^{n-1} w_i$$ where n is constant and $$w_i = {n(n-1)\over (n-i)(i+1)}+{i-1\over i+1}w_{i-1}$$

I am given the hint that $$ \sum_{i=1}^{n-1} w_i = n(n-1)\sum_{i=1}^{n-1} {1 \over (n-i)(i+1)}(1+ \sum_{j=i+1}^{n-1} \prod_{k=i+1}^{j} {k-1 \over k+1}) $$ I have no idea how to get this equation. If I know it, absolutely I can find the final solution is $$\sum_{i=1}^{n-1} w_i = (n-1)^2$$

klirk
  • 3,634
THD
  • 33

1 Answers1

2

Let have a look at the first terms.


$w_1=\dfrac{n(n-1)}{2(n-1)}+0=\dfrac{n(n-1)}{2}\left[\dfrac 1{n-1}\right]$

$w_1+w_2=w_1+\dfrac{n(n-1)}{3(n-2)}+\dfrac{1}{3}w_1=\dfrac{n(n-1)}{3(n-2)}+\dfrac 43\times\dfrac{n(n-1)}{2(n-1)}\\\phantom{w_1}=\dfrac{n(n-1)}{3}\left[\dfrac 2{n-1}+\dfrac 1{n-2}\right]$

I let you do the calculation for the next one, you will find

$w_1+w_2+w_3 = \dfrac{n(n-1)}{4}\left[\dfrac 3{n-1}+\dfrac 2{n-2}+\dfrac 1{n-3}\right]$


We can show the relation by induction:

$$\sum\limits_{k=1}^{i}w_k = \dfrac{n(n-1)}{i+1}\sum\limits_{k=1}^{i}\dfrac{k}{n-i-1+k}$$

$\begin{align}w_1&+w_2+\cdots+w_{i+1} \\\\ &= \sum\limits_{k=1}^{i}w_k+\dfrac{n(n-1)}{(n-i-1)(i+2)}+\dfrac{i}{i+2}w_i\\\\ &=\sum\limits_{k=1}^{i}w_k+\dfrac{n(n-1)}{(n-i-1)(i+2)}+\dfrac{i}{i+2}\left(\sum\limits_{k=1}^{i}w_k-\sum\limits_{k=1}^{i-1}w_k\right)\\\\ &=2\,\dfrac{i+1}{i+2}\sum\limits_{k=1}^{i}w_k-\dfrac{i}{i+2}\sum\limits_{k=1}^{i-1}w_k+\dfrac{n(n-1)}{(n-i-1)(i+2)}\\\\ &=2\,\dfrac{i+1}{i+2}\dfrac{n(n-1)}{i+1}\sum\limits_{k=1}^{i}\dfrac{k}{n-i-1+k}-\dfrac{i}{i+2}\dfrac{n(n-1)}{i}\sum\limits_{k=1}^{i-1}\dfrac{k}{n-i+k}+\dfrac{n(n-1)}{(n-i-1)(i+2)}\\\\ &=\dfrac{n(n-1)}{i+2}\left[2 \sum\limits_{k=1}^{i}\dfrac{k}{n-i-1+k}-\sum\limits_{k=1}^{i-1}\dfrac{k}{n-i+k}+\dfrac{1}{(n-i-1)}\right]\\\\ &=\dfrac{n(n-1)}{i+2}\left[2 \sum\limits_{k=1}^{i}\dfrac{k}{n-i-1+k}-\sum\limits_{k=2}^{i}\dfrac{k-1}{n-i+k-1}+\dfrac{1}{(n-i-1)}\right]\\\\ &=\dfrac{n(n-1)}{i+2}\left[\dfrac{2}{n-i}\bigg|_{k=1}+\sum\limits_{k=2}^{i}\dfrac{2k-(k-1)}{n-i-1+k}+\dfrac{1}{(n-i-1)}\right]\\\\ &=\dfrac{n(n-1)}{i+2}\left[\dfrac{2}{n-i}+\sum\limits_{k=2}^{i}\dfrac{k+1}{n-i-2+k+1}+\dfrac{1}{(n-i-1)}\right]\\\\ &=\dfrac{n(n-1)}{i+2}\left[\sum\limits_{k=3}^{i+1}\dfrac{k}{n-i-2+k}+\dfrac{2}{n-i}\bigg|_{k=2}+\dfrac{1}{(n-i-1)}\bigg|_{k=1}\right]\\\\ &=\dfrac{n(n-1)}{i+2}\left[\sum\limits_{k=1}^{i+1}\dfrac{k}{n-i-2+k}\right] \qquad\checkmark\end{align}$


Finally we can calculate the desired sum

$$\sum\limits_{k=1}^{n-1}w_k = \dfrac{n(n-1)}{(n-1+1)}\sum\limits_{k=1}^{n-1}\underbrace{\dfrac{k}{n-(n-1)-1+k}}_{=\frac kk=1}=(n-1)\sum\limits_{k=1}^{n-1} 1=(n-1)^2$$

zwim
  • 28,563
  • +1 Very nice! Can I ask, where did you learn this manioulation of sums? – Ovi Mar 04 '18 at 02:06
  • @Ovi Oh I wasn't completely confident to find the good manipulations, but it happened to work quite nicely. Mostly I got used to manipulate sums by trying to find power series solutions of ODE, at least the part about re-indexing (to keep the same power of x^n), here it was about keeping the same denominator. – zwim Mar 05 '18 at 18:42