3

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

jameselmore
  • 5,207
Letseatlunch
  • 839
  • 1
    You cant solve for "arbitrary" $F_n$, sometimes you can create a closed expression, sometimes not. I recommend you to read Concrete math or Generatingfunctionology. – Masacroso Jul 21 '15 at 20:35
  • You can start with a naive way: try to calculate explicitly some first $F$, for example, given $F_0=a$ what $F_1$, $F_2$, $F_3$, $F_4$ would be (solve by substitution)? After that you will most likely guess the solution for $F_k$. – A.Γ. Jul 21 '15 at 20:36
  • Matrices are nice to do this. You can express $F_{n+1}$ as a matrix exponent. But it is a little bit difficult to explain it without any concrete example. – mathreadler Jul 21 '15 at 20:39

3 Answers3

1

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

Ken
  • 3,751
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.$$

johannesvalks
  • 6,407
1

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.

mathreadler
  • 25,824
  • Is there anywhere I can read more about this technique? I understand matrices at a basic level but don't understand how this helps solve the problem. – Letseatlunch Aug 03 '15 at 21:38
  • I would also like to find more places to read about it. The most similar thing I've seen so far is probably https://en.wikipedia.org/wiki/Heisenberg_group. – mathreadler Aug 13 '15 at 10:52
  • So you should probably read more about groups. You can do that in some introductory course in abstract algebra. – mathreadler Aug 13 '15 at 10:52