How do you find a formula for the nth term of this sequence?
given that $x_n$$_+$$_1$ = $x_n$ + $x_n$$_-$$_1$ (Fibonacci sequence) and $x_0 = 1$ and $x_1 = 1$.
Do i complete the square on $x^2 - x - 1 = 0$, find the roots then the formula would be a linear combination of the roots?
I am just confused with this as usually the quadratic factors nicely but this one doesn't, thanks.
Linear recurrences are solved with their characteristic equation: one searches exponential solutions $(x_n)=(r^n)$, and $r$ must satisfy the characteristic equation: $$r^2=r+1\iff r=\frac{1\pm \sqrt5}2,$$ so the factorisation is $r^2-r-1=\Bigl(r-\frac{1-\sqrt 5}2\Bigr)\Bigl(r-\frac{1+\sqrt 5}2\Bigr)$.
The sequences $\;\Bigl(\dfrac{1-\sqrt5}2\Bigr)^n$ and $\;\Bigl(\dfrac{1+\sqrt5}2\Bigr)^n$ are a basis of the space of solutions of the linear recurrence. The general solution is $$u_n=\lambda\Bigl(\dfrac{1-\sqrt5}2\Bigr)^n+\mu\Bigl(\dfrac{1+\sqrt5}2\Bigr)^n,$$ and the coefficients $\;\lambda, \mu\;$ are determined with the initial conditions.