Recursive Equation.

72 Views Asked by At

We have a recursive function: $$a_n = Aa_{n-1} + Ba_{n-2} $$ We assume that $ x ^ n = a_n $. From this equality quadratic equation we have two solutions $$ \alpha, \beta, \qquad\alpha \neq \beta $$ In that case: $ \alpha ^{n-1} = a_{n-1} \vee a_{n-1} = \beta^{n-1} $. In the book, however, is written that $ a_{n-1} = c \alpha^{n-1} + d \beta^{n-1} $.

I do not know whence it follows that equality. $c,d $ are constants, but I don't understand their "nature".

2

There are 2 best solutions below

2
On

This is derived from the polynomial $a_n x^n$, so $a_n$ is the coefficient of $x^n$ and not equal to $x^n$.

And we assume that the values $a_n$ can be written as $c \alpha^n + d \beta^n$. Then we calculated them and show they indeed exist.

$\alpha$ and $\beta$ are the roots of $x^2 - Ax - B$, and $c$ and $d$ are calculated to meet the first two items in the Fibonacci sequence.

0
On

Note that the relation $a_n=Aa_{n-1}+Ba_{n-2}$ is a linear recurrence. This means that if $x_n$ and $y_n$ solve the recurrence, so does $cx_n+dy_n$. This is because:

$$A(cx_{n-1}+dy_{n-1})+B(cx_{n-2}+dy_{n-2})=c(Ax_{n-1}+Bx_{n-2})+d(Ay_{n-1}+Byx_{n-2})=cx_n+dy_n$$

This means we can find basic solutions, and combine them to form a general solution.