Proof of Fibonacci sequence

  • Thread starter majestrooo
  • Start date
  • #1

Homework Statement



Prove for k >= 0, r >= 2

F_(k+r) = F_k * F_(r-2) + F_(k+1) * F_(r-1)

Homework Equations



I wonder if one should use induction ? If so, I don't know how to do it with two variables.

If not, should I use the Fibonacci definition F_n = F_n-1 + F_n-2 in some way by substitution and renaming
subindexes?

The Attempt at a Solution



Have only tried to substitute index like k + r = m, r-2 = m etc but no luck :(
 

Answers and Replies

  • #2
CompuChip
Science Advisor
Homework Helper
4,302
47
If you fix k then you can easily do induction on r, and that works out. So if you can also show that it holds for r = 2 for this fixed k, then you have your result (k being arbitrary).
 
  • #3
Ok cool, I solved it!

Now my next problem is to prove F_2n = (F_n-1)^2 + (F_n)^2

So I tried to set r = k in the previous identity but I didn't get a solution.

Here's my attempt

r = k

F_2k = F_k * F_k-2 + F_k+1 * F_k-1

= (F_k-1 + F_k-2) * F_k-2 + F_k+1 * F_k-1

= F_k-1 * F_k-2 + (F_k-2)^2 + F_k+1 * F_k-1

= F_k-1 * F_k-2 + (F_k-2)^2 + (F_k + F_k-1) * F_k-1

= F_k-1 * F_k-2 + (F_k-2)^2 + F_k * F_k-1 + (F_k-1)^2

= (F_k-2)^2 + F_k-1 * (F_k + F_k-2) + (F_k-1)^2

= (F_k-2)^2 - (F_k-1)^2 + (F_k-1)^2 (attention " - " before the second term)

= (F_k-2)^2 = (F_k + F_k-1)^2 = (F_k)^2 + 2F_k * F_k-1 + (F_k-1)^2

So how do I get rid of th second term? ;)
 

Related Threads on Proof of Fibonacci sequence

Replies
11
Views
19K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
5
Views
2K
Replies
7
Views
3K
Replies
16
Views
10K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
1K
Replies
6
Views
1K
  • Last Post
Replies
6
Views
1K
Top