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

Question

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.

Answer 1

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

Answer 2

Such recurrences are known and have solutions similar to the proposed by you, see Wikipedia.