- #1

Avichal

- 295

- 0

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Avichal
- Start date

- #1

Avichal

- 295

- 0

- #2

DonAntonio

- 606

- 1

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

Diffy

- 441

- 0

Duh, DonAntonio.. its *THE* Fibonacci nth term proof.

- #4

jbriggs444

Science Advisor

Homework Helper

- 11,583

- 6,240

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

- 11,583

- 6,240

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

This allows you to find the n-th term directly.

- #7

Avichal

- 295

- 0

Substituting we get x

But then we say solution is of the form ax

- #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

a_{n}=x^{n}, 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.

into the quadratic you just described.

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

a

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

MHB

- 16,350

- 256

As jbriggs444 already said:

x

So is x

And so is any linear combination thereof.

If you fill in for instance bx

The next step is to find out which linear combination fits with the fact that the first 2 terms are 1.

- #10

Avichal

- 295

- 0

Thank you - its clear now.

Share:

- Last Post

- Replies
- 3

- Views
- 455

- Last Post

- Replies
- 4

- Views
- 896

- Replies
- 10

- Views
- 1K

- Replies
- 15

- Views
- 536

- Last Post

- Replies
- 7

- Views
- 740

- Replies
- 10

- Views
- 849

- Replies
- 5

- Views
- 447

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 1K

- Replies
- 12

- Views
- 2K