# General recurrence $f(n)=\alpha(n)+\beta(n)f(n-1)$

While computing certain integrals, like $$I_n=\int\frac{\mathrm dx}{(ax^2+b)^{n+1}}$$ I frequently come up with recurrence relations (AKA reduction formulae) like $$I_n=\frac{x}{2bn(ax^2+b)^n}+\frac{2n-1}{2bn}I_{n-1}$$ All of which are (so far in my experience) of the form $$f(n)=\alpha(n)+\beta(n)f(n-1)$$ Where $$\alpha,\beta$$ are functions of $$n$$ (and other parameters/variables, but that doesn't really matter). And the recurrence has an explicit base case $$f(0)=N$$.

And I am trying to find a closed form/solution to this general recurrence.

Attempt:

\begin{align} f(n)=&\alpha(n)+\beta(n)f(n-1)\\ =&\alpha(n)+\beta(n)\alpha(n-1)+\beta(n)\beta(n-1)f(n-2)\\ =&\alpha(n)+\beta(n)\alpha(n-1)+\beta(n)\beta(n-1)\alpha(n-2)+\beta(n)\beta(n-1)\beta(n-2)f(n-3)\\ =&\cdots\\ =& N\prod_{r=1}^{n}\beta(r)+\sum_{k=0}^{n-1}\alpha(n-k)\prod_{i=1}^{k}\beta(k-i+1)\text{?}\tag{1} \end{align} Of course this conjecture is based on the continuation of a pattern, but obviously that is not the most mathematically rigorous method. But the problem is, I don't know how else one would go about proving this sort of thing. Could I have some help? Thanks.

• If you have a pattern in $n \in \mathbb{N}$, why not try mathematical induction? Jan 21, 2019 at 21:17
• @SangchulLee I admittedly do not know how to use induction Jan 22, 2019 at 1:30

Okay I finally learned how to use induction. We see that $$(1)$$ holds for $$n=1$$. So our hypothesis is, if $$(1)$$ holds for some $$n\geq1$$, then $$(1)$$ holds for $$n+1$$.
So for some $$n\geq1$$ $$f(n)=f(0)\prod_{k=1}^{n}\beta(k)+\sum_{k=0}^{n-1}\alpha(n-k)\prod_{j=1}^{k}\beta(n-j+1)$$ And by definition \begin{align} f(n+1)&=\alpha(n+1)+\beta(n+1)\left[f(0)\prod_{k=1}^{n}\beta(k)+\sum_{k=0}^{n-1}\alpha(n-k)\prod_{j=1}^{k}\beta(n-j+1)\right]\\ &=\alpha(n+1)+f(0)\prod_{k=1}^{n+1}\beta(k)+\sum_{k=0}^{n-1}\alpha(n-k)\beta(n+1)\prod_{j=1}^{k}\beta(n-j+1)\\ &=f(0)\prod_{k=1}^{n+1}\beta(k)+\alpha(n+1)+\sum_{k=0}^{n-1}\alpha(n-k)\prod_{j=0}^{k}\beta(n-j+1)\\ &=f(0)\prod_{k=1}^{n+1}\beta(k)+\sum_{k=0}^{(n+1)-1}\alpha[(n+1)-k]\prod_{j=1}^{k}\beta[(n+1)-j+1 \end{align} Which is $$(1)$$. QED