3
$\begingroup$

Here is the official theorem I'll use: enter image description here

Since the Fibonacci sequence is defined as $F_n=F_{n-1}+F_{n-2}$, we solve the equation $x^2-x-1=0$ to find that $r_1 = \frac{1+\sqrt 5}{2}$ and $r_2 = \frac{1-\sqrt 5}{2}$

So we have $F_n = c_1\left(\frac{1+\sqrt 5}{2}\right)^n + c_2\left(\frac{1-\sqrt 5}{2}\right)^n$

We know that $F_0 = F_1 = 1$. So we can solve the following system to find the values of $c_1$ and $c_2$:

$1 = c_1 + c_2$

$1 = c_1\left(\frac{1+\sqrt 5}{2}\right) + c_2\left(\frac{1-\sqrt 5}{2}\right)$

Solving this system does not give $c_1 = 1/\sqrt5, c_2 = -1/\sqrt 5$ , even though that is apparently the right answer, i.e. the closed form of the Fibonacci sequence is apparently $$\frac1{\sqrt 5}\left(\frac{1+\sqrt 5}{2}\right) -\frac1{\sqrt 5}\left(\frac{1-\sqrt 5}{2}\right)$$

Where did I go wrong? Why doesn't solving the system of equations give me $c_1 = 1/\sqrt5, c_2 = -1/\sqrt 5$?

$\endgroup$
11
  • 2
    $\begingroup$ Well, with the latter values we have $c_1+c_2=0$. So perhaps they were using $F_0=0,F_1=1$ as initial conditions. That's standard anyway. $\endgroup$ Commented Nov 18, 2019 at 21:32
  • $\begingroup$ See math.stackexchange.com/questions/65011/… $\endgroup$ Commented Nov 18, 2019 at 22:00
  • $\begingroup$ The initial values for the Fibonacci sequence are defined as either $F_0=0,F_1=1$ or $F_1=F_2=1$ (of course, they both produce the same sequence). Maybe you confused the two ways? It would be easier to substitute $n=0$ and $n=1$. $\endgroup$ Commented Nov 18, 2019 at 23:13
  • $\begingroup$ @lulu Thank you for the help!, so does the closed form of the Fibonacci sequence depend on what you choose $F_0$ and $F_1$ to be? That would be weird, since no matter your choice of $F_0$ and $F_1$ you still end up with the same sequence... $\endgroup$ Commented Nov 19, 2019 at 16:14
  • $\begingroup$ @bjorn93 Thank you for the response! So why is it the choice of initial values changes the closed form of the sequence? As you said, the choice of initial values doesn't change the sequence itself, so how can the closed form change? $\endgroup$ Commented Nov 19, 2019 at 16:16

1 Answer 1

Reset to default
1
$\begingroup$

Let's see...

$$f_n = \left\{ \begin{array}{ll} 0 & \text{ for } n = 0 \\ 1 & \text{ for } n = 1 \\ f_{n-1} + f_{n-2} & \text{ for } n>1 \end{array} \right.$$

Now, the recursion can be written as $$f_n - f_{n-1} - f_{n-2} = 0,$$ so characteristic equation is $$x^2-x-1=0.$$ Now, the roots of the equation are $$X_{1,2} = \frac{1 \pm \sqrt{5}}2,$$ so general solution is $$f_n = C_1\cdot\left(\frac{1 + \sqrt{5}}2\right)^n + C_2\left(\frac{1 - \sqrt{5}}2\right)^n$$ From the $f_1$ and $f_2$ we get \begin{eqnarray} 0 &=& C_1 + C_2 \\ 1 &=& C_1\left(\frac{1 + \sqrt{5}}2\right) + C_2\left(\frac{1 - \sqrt{5}}2\right) \end{eqnarray} From the first equation we get $$C_2 = -C_1,$$ so \begin{equation} 1 = C_1\left(\frac{1 + \sqrt{5}}2\right) -C_1\left(\frac{1 - \sqrt{5}}2\right) \end{equation} Now, we have $$C_1\left[\frac{1 + \sqrt{5}}2 - \frac{1 - \sqrt{5}}2\right] = 1$$ or $$C_1\cdot\sqrt{5} =1$$ So, $$C_1 = \frac{1}{\sqrt{5}}.$$ Now, $$C_2 = -\frac{1}{\sqrt{5}}.$$ The particular solution for the equation is therefore $$f_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}2\right)^n - \left(\frac{1-\sqrt{5}}2\right)^n\right]$$

$\endgroup$
1
  • $\begingroup$ I have noticed the reason the root fives disappear is roughly due to the fact that if n is odd, then a root five is left behind but the root five in the denominator cancels it out. For the even powers, they cancel by subtraction symmetry between the 1+root(5) and 1-root(5) components. So always, the sequence produced by f_n is rational regardless of whether we use root(5) or root(7) or any root(k). But why do some produce whole numbers. For example, 5, 9, and 13 produce whole number sequences but 3 or 7 produce only rational? $\endgroup$ Commented Feb 11 at 16:34

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.