Finding an explicit formula for a recursive sequence.

Question

How to show that the recurrent formula

$$A_n=A_{n-1} + A_{n-2} +4.$$

gives a sequence of the form $f(n)=cr^n+cr^n$?

The only way we are allowed to solve it, is with the quadratic formula $(r^2-r-1)$...

Answer 1

Hint: Consider $B_n = A_n+4$. Then $B_n=B_{n-1}+B_{n-2}$, which is a famous recurrence.

Answer 2

Consider $B_n=A_n+4$, to get $B_n=B_{n-1}+B_{n-2}$.

Now you can solve the chactaristic equation $r^2-r-1$.

This gives $r=\frac{1+\sqrt{5}}{2}$, $r=\frac{1-\sqrt{5}}{2}$.

Therefore we have $$B_n= A \left(\frac{1+\sqrt{5}}{2}\right)^n+ B \left(\frac{1-\sqrt{5}}{2}\right)^n$$

Therefore

$$A_n= A \left(\frac{1+\sqrt{5}}{2}\right)^n+ B \left(\frac{1-\sqrt{5}}{2}\right)^n -4$$

Where $A,B$ depend on your initial conditions.

Answer 3

More generally, suppose that $a_n =\sum_{i=1}^k c_i a_{n-k} + u $. To get rid of the constant term, so this will be a homogeneous recurrence, let $a_i =b_i-v $.

Then $b_n-v =\sum_{i=1}^k c_i (b_{n-k}-v) + u =\sum_{i=1}^k c_i b_{n-k}-v\sum_{i=1}^kc_i + u $ or $b_n =\sum_{i=1}^k c_i b_{n-k}-v(-1+\sum_{i=1}^kc_i) + u $

Therefore, if we choose $v = \dfrac{u}{-1+\sum_{i=1}^kc_i } $, this is what we want.

Of course this assumes that $\sum_{i=1}^kc_i \ne 1 $. If $\sum_{i=1}^kc_i = 1 $, we have to do something else.