2

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

Jimmy R.
  • 35,868
user180834
  • 1,453

2 Answers2

1

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.

Pieter21
  • 3,475
  • I can't understand this polynomial and why $a_n$ is coefficient. Help me – user180834 Oct 25 '14 at 22:18
  • This is the definition that will lead to the required results. We define polynomials $a_n x^n$ where $a_n$ is the $n^{th}$ number in the sequence and $x^n$ is the $n^{th}$ polynomial. – Pieter21 Oct 26 '14 at 21:57
1

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.

Mark Bennet
  • 100,194