In answering a question myself I have ended up with a summation of the form: $$a_n=\frac{n(n+3)}{2}a_{n-1}+\frac{n(n+1)}{2}$$ I am unsure of how to solve this type of summation such that I have it in the form: $$a_n=f(a_0,n)$$ I know that problems of this form can be solved as I have seen it in the Fibonacci sequences and other cases but I am not sure how I go about doing this, I will link the original question here. Thanks!

Evidence of my attempt so far and how I got in this form can be found at the original question


I've found a formula here which talks about how to solve first order non-homogeneous recurrence relations, which states for a series in the form: $$a_{n+1}-f_na_n=g_n$$ we can say: $$a_n=\left(\prod_{k=0}^{n-1}f_k\right)\left(A_0+\sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^mf_k}\right)$$ So I will try to use this

  • $\begingroup$ Do you know about generating functions? $\endgroup$ – kccu May 6 '19 at 22:55
  • $\begingroup$ Not really no, although by searching it, it seems it could be used to solve problems of this form $\endgroup$ – Henry Lee May 6 '19 at 22:56
  • $\begingroup$ Yes, that would be my approach. $\endgroup$ – kccu May 6 '19 at 23:00
  • $\begingroup$ Is there a way you could explain how to apply it when it is in this form? I can't find an example where $a_{n-1}$ is multiplied by a function of $n$ $\endgroup$ – Henry Lee May 6 '19 at 23:02

Let $A(x)=\sum_{n=0}^\infty a_nx^n$. Your recurrence can be re-written as: $$a_{n+1}=\frac{(n+1)(n+4)}{2}a_n + \frac{(n+1)(n+2)}{2} = \frac{(n+1)(n+2)}{2}a_n + (n+1)a_n + \frac{(n+1)(n+2)}{2}.$$ Now we multiply through by $x^n$ and sum from $n=0$ to $\infty$: \begin{align*} \sum_{n=0}^\infty a_{n+1}x^n&= \frac{1}{2}\sum_{n=0}^\infty (n+1)(n+2)a_nx^n + \sum_{n=0}^\infty (n+1)a_nx^n + \frac{1}{2}\sum_{n=0}^\infty (n+1)(n+2)x^n\\ \frac{1}{x}\sum_{n=0}^\infty a_{n+1}x^{n+1}&= \frac{1}{2}\sum_{n=0}^\infty (n+1)(n+2)a_nx^n + \sum_{n=0}^\infty (n+1)a_nx^n + \frac{1}{2}\sum_{n=0}^\infty (n+1)(n+2)x^n\\ \frac{1}{x}(A(x)-a_0)&= \frac{1}{2} \frac{d^2}{dx^2}A(x) + \frac{d}{dx}A(x) + \frac{1}{2}\frac{d^2}{dx^2} \Bigg(\underbrace{\sum_{n=0}^\infty x^n}_{\frac{1}{1-x}}\Bigg)\\ \frac{1}{x}(A(x)-a_0)&= \frac{1}{2} A''(x) + A'(x) + \frac{1}{(1-x)^3}. \end{align*} So now you would need to solve this second-order non-homogeneous differential equation.

  • $\begingroup$ That is great, thank you! $\endgroup$ – Henry Lee May 6 '19 at 23:40

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.