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.
Best Answer
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