I have a recurrence equation and I have no idea how to solve it. $$a(n)=(1-\frac{1}{n}+\frac{X}{n})a(n-1)+\frac{2}{n}$$

$$a(1)=1$$ where X is a constant

I tried to put it into Wolfram and I got the following solution:


It is the correct solution. But Wolfram didn't give any intermediate steps so I am still puzzled how it is solved.

Any hints or comments are welcomed. Thanks in advance.

  • $\begingroup$ I guess that this comes from Pochhammer symbols. Let $t=X-1$ and comute the very first terms to notice a pattern. $\endgroup$ – Claude Leibovici Jul 5 '18 at 8:05

Let $\,k=X-1 \ne 0\,$, then the recurrence is $\displaystyle\,a_n=\frac{n+k}{n}a_{n-1}+\frac{2}{n}\,$.

Multiplying by $\,k\,$ and defining $\,b_n = k a_n\,$ gives $\displaystyle\,b_n=\frac{n+k}{n}b_{n-1}+\frac{2k}{n}\,$.

Adding $\,2\,$ on both sides gives $\displaystyle\,b_n+2=\frac{n+k}{n}b_{n-1}+\frac{2k}{n}+2=\frac{n+k}{n}(b_{n-1}+2)\,$.

Then $\,c_n=b_n+2\,$ telescopes to:

$$ \begin{align} c_n &= \frac{n+k}{n}c_{n-1} \\ &=\frac{(n+k)(n+k-1)}{n(n-1)} c_{n-2} \\ &\ldots \\ &= \frac{(n+k)(n+k-1)\ldots(k+1)}{n(n-1)\ldots 2} c_{1} \\ \end{align} $$

Substituting back into $\,a_n=\dfrac{c_n-2}{k}\,$ gives an expression equivalent to the posted one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.