Fibonacci sequence - how to prove a_n=1/sqrt(5) ((1+sqrt(5)/2)^n-(1-sqrt(5)/2)^n) without incduction

grabrovi0u

grabrovi0u

Answered question

2022-10-31

Fibonacci sequence - how to prove a n = 1 5 ( ( 1 + 5 2 ) n ( 1 5 2 ) n ) without induction

Answer & Explanation

benyaep17

benyaep17

Beginner2022-11-01Added 11 answers

You can use generating functions. Let F n be the Fibbonacci sequence defined as
F 0 = 1 F 1 = 1 F n = F n 1 + F n 2 ; n 2
Let
F ( x ) = n 0 F n x n
be its generating function. Then
( 1 x x 2 ) F ( x ) = n 0 F n x n n 0 F n x n + 1 n 0 F n x n + 2
And by the recursion the left hand side is 1+1-1+0 so
( 1 x x 2 ) F ( x ) = 1
Now use that
x 2 + x 1 = ( x + φ ) ( x φ 1 )
and the geometric expansion
1 a x = k = 0 a 1 k x k
plus simple fractions to get what you want.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?