How can I write this recurrence in terms of summations and products?

Question

I have the following recurrence formula: $$ w_i = \frac{n(n-1)}{(n-i)(i+1)} + \frac{i-1}{i+1}w_{i-1} $$ that is defined for $i = 1,\cdots, n$.

I would like to write it in terms of just $i$ and $n$, without the $w_{i-1}, so I imagine the formula would end up being a summation and a product.

I expanded a little bit just to identify some structure in the recurrence \begin{align} w_i =\frac{n(n-1)}{(n-i)(i+1)} + \frac{i-1}{i+1}(\frac{n(n-1)}{(n-(i-1))(i)} + \frac{i-2}{i}w_{i-2}) \\ w_i =\frac{n(n-1)}{(n-i)(i+1)} + \frac{i-1}{i+1}(\frac{n(n-1)}{(n-(i-1))(i)} + \frac{i-2}{i}(\cdots (\cdots (\cdots (\cdots))))) \\ \end{align}

But I'm having a hard time wrapping my head around all the nested parenthesis, and how to write this succinctly with $\sum$ and $\prod$. Could someone help?

It might help to work out $w_1,w_2,w_3,\ldots$ and see if you notice any patterns. Then you might be able to guess a closed form that could be proved by induction. — A. Goodier, May 08 '20 at 21:01
Does this answer your question? How to calculate the summation of $w_i$, where $w_i = {n(n-1)\over (n-i)(i+1)}+{i-1\over i+1}w_{i-1}$ — zwim, May 08 '20 at 21:09
I think that rewriting $\frac{n(n-1)}{(n-i)(i+1)}$ and $\frac{i-1}{i+1}$ as for example $f(n,i)$ and $g(i)$ can simplify everything and make easier working this function out. — Jakub Pawlak, May 08 '20 at 21:13
Look at the link I provided this reduces to the simpler recurrence $\sum\limits_{i=1}^n w_i=n^2$ — zwim, May 08 '20 at 21:15
@zwim Sure does. Although in this case I wasn't directly looking for $\sum w_i$ but that helps me approach the problem in a different way. I took a different approach and found that the recurrence relation for $w_i$ is actually a non-homogeneous difference equation with a known solution. — user5965026, May 08 '20 at 23:50

score 1 · Answer 1 · answered May 09 '20 at 04:59

1

Let $w_i=\frac{z_i}{i(i+1)}$ to make $$z_{i}=z_{i-1}+\frac{i (n-1) n}{n-i}$$ which let suspecting harmonic numbers in the solution.

The remaining was done using a CAS which gave $$z_i=C-i(n-1)+n(n-1) \left(H_{-n}-H_{i-n}\right)$$

answered May 09 '20 at 04:59

Claude Leibovici

260,315

How can I write this recurrence in terms of summations and products?

1 Answers1