Looking at the method for solving recurrence relations given on Wikipedia here, I found myself confused by some aspects of the method. To save people tabbing backwards and forwards, here is what it says:
For [a] general first-order non-homogeneous linear recurrence relation with variable coefficients:
$$a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,$$
there is [...] a nice method to solve it:
$$a_{n+1}-f_{n}a_{n}=g_{n}$$ $${\frac {a_{n+1}}{\prod_{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}$$ $${\frac {a_{n+1}}{\prod_{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}$$
Let
$$A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},$$
Then
$$A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}$$ $$\sum_{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}$$ $${\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}$$ $$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}^{m}f_{k}}}\right)$$
If we apply the formula to $a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}$ and the take the limit $h \to 0$, we get the formula for first order linear differential equations with variable coefficients; the sum becomes an integral, and the product becomes the exponential function of an integral.
I have questions:
- Are $f_n$ and $g_n$ functions or sequences of coefficients? I note that the heading for the section states that this is a discussion of linear recurrence relations. But obviously, if all we can discover are specific coefficients $f_n,g_n$ for some chosen $n$, then we are no closer to finding a general pattern for the sequence $a_1,a_2,...$
- What is meant by $f_{n h}$ and $g_{nh}$? If the answer to question 1 is that they are functions, then do we have $f_{nh}=f(n+h)$? It's not at all clear.
- Basically, I just don't understand that last paragraph. It feels like we get to the tricky bit and then hand-waving takes over from maths.
What I am after is a clear understanding of what happens after the last equation in the section. If it's not possible to work the last part through in a general sense, then I'd very much appreciate a specific example - but the general approach is preferable.
Thanks in advance.
