How to solve recursive equations $F_{n+1} = F_{n} \cdot g + h$

Question

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$$

Answer 1

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.$$

Answer 2

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).$$

Answer 3

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.