Fibonacci nth term

  • Thread starter Avichal
  • Start date
  • #1
292
0

Main Question or Discussion Point

I have a doubt regarding its proof. First we assume that solution is of the form x^n-then we solve the quadratic equation and get two values of x-x1 & x2. After that we say solution is of the form ax1^n+bx2^n contradicting our previous assumption that solution is of the form x^n
 

Answers and Replies

  • #2
606
1
I have a doubt regarding its proof. First we assume that solution is of the form x^n-then we solve the quadratic equation and get two values of x-x1 & x2. After that we say solution is of the form ax1^n+bx2^n contradicting our previous assumption that solution is of the form x^n

Are you assuming we'll be able to guess what you're talking about, what's [itex]\,x_n\,[/itex], what quadratic equation you're talking

about, etc., or you really think everybody knows this? I mean, I guess you're talking of the quadratic that has the golden mean

as one of its roots and from which the general term for the n-th Fibonacci element is gotten,. but it'd be nice if you write down

exactly what's bothering you.

DonAntonio
 
  • #3
441
0
Duh, DonAntonio.. its THE Fibonacci nth term proof.
 
  • #4
jbriggs444
Science Advisor
Homework Helper
2019 Award
7,969
2,827
It has been a lot of years since we covered this stuff in school...

The Fibonacci series is an example of a sequence that fits a linear, homogeneous, second-order recurrence relation. That is, each term is expressible as:

f(n) = k1 * f(n-1) + k2 * f(n-2)

For the Fibonacci series, k1 = 1 and k2 = 1.

If one assumes that _a_ solution is f(n) = x^n for some x then one can derive from this the quadratic equation:

x^2 = x + 1

Solving this quadratic yields two roots. One is the golden ratio. The other is the negation of the inverse of the golden ratio. And indeed, both roots work as values for x such that x^n fits the given recurrence relation.

I no longer remember the argument that establishes that these two solutions (and all linear combinations thereof) are the only solutions to the recurrence.
 
  • #5
jbriggs444
Science Advisor
Homework Helper
2019 Award
7,969
2,827
I no longer remember the argument that establishes that these two solutions (and all linear combinations thereof) are the only solutions to the recurrence.
Replying to myself.

One argument is simple: Any particular instance of the Fibonacci series is uniquely determined by its first two terms. Those first two terms also uniquely determine a linear combination of the two solutions that were discovered. It follows that there can be no other solutions.
 
  • #6
Bacle2
Science Advisor
1,089
10
You can also write down the recurrence using a matrix and then diagonalize the matrix.

This allows you to find the n-th term directly.
 
  • #7
292
0
I'll write down my doubt in detail. Fibonacci series is : an = an-1 + an-2. We assume that solution to this equation is of the form an = xn.
Substituting we get x2 - x - 1 = 0 and get two values of x say x1 and x2.

But then we say solution is of the form ax1n + bx2n for some a and b contradicting our previous assumption that solution is xn.
 
  • #8
Bacle2
Science Advisor
1,089
10
I don't think that is how the method is defined. You transform your recursion

into the quadratic you just described.

Actually, it seems clear that the answer would not be of the form

an=xn, since,for one thing, your 1st and 2nd terms are both

equal to 1.

EDIT:For some weird reason, I was assumming the x_i were integer-valued. Clearly, they're not, and

under these conditions, my comments are nonsense. Sorry.
 
Last edited:
  • #9
I like Serena
Homework Helper
6,575
176
Hi Avichal! :smile:

As jbriggs444 already said:

x1n is a solution of your recurrence relation - without the boundary conditions that the first 2 terms are 1.
So is x2n.
And so is any linear combination thereof.

If you fill in for instance bx2n in the recurrence relation, you should see that it pans out.

The next step is to find out which linear combination fits with the fact that the first 2 terms are 1.
 
  • #10
292
0
Thank you - its clear now.
 

Related Threads for: Fibonacci nth term

  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
5
Views
1K
Replies
4
Views
547
Replies
3
Views
3K
Replies
3
Views
2K
Top