Recently I am working on recurrence relation and I have gathered the following.

  1. Fibonacci sequence
  2. Solving linear homogeneous recurrence relation by characteristics equation

So I attempted to work on the closed form of Fibonacci sequence by myself. However, it seems to contradict to another source attached below indicating the closed form of Fibonacci sequence. May I know what's wrong?

Solution technique:

  1. Establish the characteristics equation and its roots. $$r^2-r-1=0$$ $$r=\frac{1\pm\sqrt5}{2}$$
  2. Assume $f_n=c_1r_1^n+c_2r_2^n$, where $r_1$ and $r_2$ are distinct roots in this case.
  3. Find $c_1,\;c_2$ $$r_1=\frac{1+\sqrt5}{2},\;r_2=\frac{1-\sqrt5}{2}$$ $$f_0=c_1r_1^0+c_2r_2^0=c_1+c_2=1$$ $$f_1=c_1r_1^1+c_2r_2^1=c_1r_1+c_2r_2=2$$ $$\left[\begin{array}{cc|c}1&1&1\\\frac{1+\sqrt5}{2}&\frac{1-\sqrt5}{2}&2\end{array}\right]=\cdots=\left[\begin{array}{cc|c}1&0&\frac{5+3\sqrt5}{10}\\0&1&\frac{5-3\sqrt5}{10}\end{array}\right] $$ $c_1\neq\frac{1}{\sqrt5},\;c_2\neq-\frac{1}{\sqrt5}$ as indicated in the below closed form, what's wrong in my derivation?

The closed form I would like to replicate using characteristic equation

  • $\begingroup$ What number is $f_1$? $\endgroup$ Feb 17 '20 at 4:23
  • $\begingroup$ I am not sure whether is $f_0=1$ or $f_0=0$...May I know the convention also? $\endgroup$
    – Andes Lam
    Feb 17 '20 at 4:24
  • 1
    $\begingroup$ Usually $f_0$ is taken to be $0$ and $f_1=f_2=1$ $\endgroup$ Feb 17 '20 at 4:25
  • $\begingroup$ I think we should have $\{\frac{1}{\sqrt{5}}⋅\left(\frac{1+\sqrt{5}}{2}\right)^n,\frac{1}{\sqrt{5}}⋅\left(\frac{1-\sqrt{5}}{2}\right)^n\}$ with $n=2$ in the first row and $n=3$ in the second row $\endgroup$
    – Matt Groff
    Feb 17 '20 at 4:29

The usual convention is $f_0=0, f_1=f_2=1$. Using your equations $$c_1+c_2=0\\c_1r_1+c_2r_2=1\\ c_1\frac{1+\sqrt 5}2+c_2\frac{1-\sqrt 5}2=1\\ \frac {\sqrt 5}2(c_1-c_2)=1\\ c_1=\frac 1{\sqrt 5}\\c_2=-\frac 1{\sqrt 5}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.