How to get a general rule from the recursive definition

Question

Assume we have an arithmetic sequence $f_n$ that has a non-recursive definition as follows: $$f_n=2n+1$$ This sequence can also be defined recursively: $$f_n=2+f_{n-1}$$ $$f_0=1$$ The same can be done if we assume f_n is a geometric sequence: $$f_n=3^n$$ $$f_n=3f_{n-1}$$ $$f_0=1$$ Note that if either the non-recursive rule or the recursive definition of a geometric sequence or an arithmetic sequence is known, the other definition can be derived. This is possible, however, only when the sequence is known to be distinctly arithmetic or geometric. In other words, the recursive definition should be $f_n=a*f_{n-1}$ or $f_n=a+f_{n-1}$. My question is that is there a proof if it possible to derive a general rule for a sequence with the combined recursive definitions of an arithmetic and a geometric sequence which looks like: $$f_n=af_{n-1}+b$$ $$f_0=c$$

If it is possible, what would be the way to derive the general rule ?

P.S. I am not that much informed in this area, and because of this, I would be very glad if you point out the unclear or wrong parts of the question. Constructive feedback is always useful :)

Answer 1

If $a=1$ we have an arithmetic progression with $f_n=bn+c$

Otherwise it would be easier if we could find a $k$ such that $g_n=f_n+k$ and $g_n=ag_{n-1}$ making $g_n=a^ng_0$

so we want $f_n+k = a(f_{n-1}+k)$ while we know $f_n = af_{n-1}+b$

and this means we need $k=\frac{b}{a-1}$ and we do not have division by zero as $a \not=1$, so $$f_n=g_n -\frac{b}{a-1} = a^n g_0 -\frac{b}{a-1}= a^n\left(c+\frac{b}{a-1}\right)-\frac{b}{a-1} $$

Answer 2

I'm honestly not what the answer is, but you may want to check out the well-written wikipedia post on recurrence relations.

Answer 3

First look at a relation of the form:

$$f_n=c_1f_{n-1}+c_2f_{n-2}+\ldots +c_rf_{n-r}+k$$

where the $c_i$ and $k$ are constants. The first thing to do is to get rid of the constant term $k$. This is done by setting:

$$g_i=f_i - \frac{k}{1 -c_1-c_2\ldots -c_r}$$

and solving:

$$g_n=c_1g_{n-1}+c_2g_{n-2}+\ldots +c_rg_{n-r}$$

This is known as a homogeneous linear recurrence relation and the method of solution is given here: https://brilliant.org/wiki/linear-recurrence-relations/ The general method is somewhat too complicated to give here.

Once you have the solution for $g_n$ you can convert it into one for $f_n$.