How to solve recursive equations $F_{n+1} = F_{n} \cdot g + h$ Sorry if this is a duplicate or easy (a lot of the other 'how do i solve recursive equation' questions were for more complex equations). How can I solve this for arbitrary $F_n$ with arbitrary constants $c_1$ and $c_2$.
$$F_{n+1} = F_{n} \cdot c_1 + c_2$$
Also does it matter if $c_1$ and $c_2$ are constants or would it work if they were functions themselves such as:
$$F_{n+1} = F_{n} \cdot g + h$$
 A: In the case of the constants, assuming $F_0 = s$, a simple induction proof will yield that for each $n \in \mathbb{N}$,
$$F_n = c_1^ns + c_2\left(\sum_{i = 0}^{n-1} c_1^i\right).$$
A: Given
$$
F_{n+1} = F_n c_1 + c_2.
$$
Case $c_1 \ne 1$
We can write
$$
F_{n} = G_{n} - \zeta.
$$
Then we obtain
$$
\underbrace{G_{n+1} - \zeta}_{\displaystyle F_{n+1}} =
\Big( \underbrace{G_{n} - \zeta}_{\displaystyle F_{n}} \Big) c_1 + c_2,
$$
so
$$
G_{n+1} = G_{n} c_1 + \underbrace{\zeta - \zeta c_1 + c_2}_{\displaystyle 0},
$$
thus
$$
c_1 \ne 0 : \zeta - \zeta c_1 + c_2 = 0 \Rightarrow \zeta = \frac{c_2}{c_1-1}.
$$
Let $c_1 \ne 1$, then we write
$$
F_{n} = G_{n} - \frac{c_2}{c_1-1}.
$$
Put this in recursion relation and we get
$$
G_{n+1} - \frac{c_2}{c_1-1} = G_{n} c_1 - \frac{c_1 c_2}{c_1-1} + c_2.
$$
Whence we obtain
$$
G_{n+1} = G_{n} c_1.
$$
Therefore
$$
G_{n} = G_{0} c_1^n.
$$
Going back, we get


$$
F_{n} = \Big( F_{0} + \frac{c_2}{c_1-1} \Big) c_1^n
     - \frac{c_2}{c_1-1}.
$$



Simple check:
$$
\begin{array}{rclc}
F_{n+1} &=& \displaystyle \Big( F_{0} + \frac{c_2}{c_1-1} \Big) c_1^{n+1}
     - \frac{c_2}{c_1-1}.\\
F_{n} c_1 &=& \displaystyle \Big( F_{0} + \frac{c_2}{c_1-1} \Big) c_1^{n+1}
     - \frac{c_1 c_2}{c_1-1}.\\
&&&-\\
\hline\\
F_{n+1} - F_{n} c_1 &=& \displaystyle
     \frac{c_1 c_2}{c_1-1} - \frac{c_2}{c_1-1} = c_2.
\end{array}
$$

More general, we can write



$$F_{n} = \Big( F_1 - F_0 c_1 \Big) c_2 \frac{c_1^n-1}{c_1-1} + F_0 c_1^n.$$


A: You can solve these with matrix powers.
$$A_0 = \left(\begin{array}{ccc}g&0&0\\h&0&0 \\F_0&1&0 \end{array}\right)$$
we see that
$$({A_0}^2)_{3,1} = gF_0+h+0 = F_1$$
Just keep multiplying to the left with $A_0$ and you will get next element at position (3,1) in the matrix.
Maybe you need to calculate $g$ or $h$ as a function of $n$, but there are ways do to this with matrix multiplication for many types of functions.
