how to find nth term in a fibonacci series or sum of a series of fibonacci numbers

Question

A series is given as $1,6,7,13,20,33,.......$ and so on Find the sum of first 52 terms?

what i know is

The sum of the first n Fibonacci numbers is the [(n + 2)nd Fibonacci number - 1] . So the sum of first 52 fibonacci numbers is [54th fibonacci number - 1]

now i have no clue about how to find nth no of a Fibonacci series . is there any method to evaluate nth term in Fibonacci series? here how can i find 54th term of the series?

note :: its a aptitude exam's question and on an average 1-2 mins allowed per question.so is there any faster method of finding nth term in a fibonacci series. i want to avoid the manual search procedure because its too time taking procedure

Answer 1

If $a_{n+1} = a_n+a_{n-1}$, $a_n = a_{n+1}-a_{n-1}$. Therefore

$\begin{align} \sum_{k=0}^n a_k &=a_0+\sum_{k=1}^n a_k\\ &=a_0+\sum_{k=1}^n (a_{k+1}-a_{k-1})\\ &=a_0+\sum_{k=1}^n a_{k+1}- \sum_{k=1}^na_{k-1}\\ &=a_0+\sum_{k=2}^{n+1} a_{k}- \sum_{k=0}^{n-1}a_{k}\\ &=a_0+(\sum_{k=2}^{n-1} a_{k}+a_n+a_{n+1})- (a_0+a_1+\sum_{k=2}^{n-1}a_{k})\\ &=a_0+(a_n+a_{n+1})- (a_0+a_1)\\ &=a_{n+2}- a_1\\ \end{align} $

This is your statement about the sum, but it is true for any sequence that satisfies the Fibonacci recurrence, not just the standard one.

So, you only ("only"!) have to compute $a_{n+2}$.

As shown in the standard way by Adi Dani, the generating function for the $a_n$ is $F(x)=\dfrac{1+5x}{1-x-x^2}$.

You then have to write $1-x-x^2 =(1-ax)(1-bx)$ in the usual standard way (all this is the traditional way to get Binet's formula), get $a$ and $b$, find $c$ and $d$ such that $\dfrac1{(1-ax)(1-bx)} =\dfrac{c}{1-ax}+\dfrac{d}{1-bx} $, write $F(x) =\dfrac{1+5x}{1-x-x^2} =(1+5x)\big(\dfrac{c}{1-ax}+\dfrac{d}{1-bx}\big) $, and get the power series for $F(x)$ using $\dfrac{1}{1-rx} =\sum_{j=0}^{\infty} r^j x^j $.

Have at it.

Answer 2

Oh, well the 54th term of the series can be found as follows: compute $\pmatrix{1&1\\\ 1&0}^{53}$ then multiply by the transpose of (6,1) , the vector will be to the right of the matrix. There are fast multiplication schemes for computing the matrix.

$\pmatrix{1&1\\\ 1&0}^{32}$ * $\pmatrix{1&1\\\ 1&0}^{16}$ * $\pmatrix{1&1\\\ 1&0}^{4}$ * $\pmatrix{1&1\\\ 1&0}$ * (6,1)^T

Answer 3

I know that this doesn't completely answer your question, but it gives you what you want for the first half of the question title. For large $n$, it sounds like a closed form expression is more appropriate than computing larges sums:

The $n$-th Fibonacci number $F_n$, using the floor function, is given by:

$$ F_n = \Bigg\lfloor \frac{{\phi}^n}{\sqrt{5}} + \frac{1}{2} \Bigg \rfloor, \quad n \geq 0$$

Alternatively, you could use the nearest integer function:

$$ F_n = \left[ \frac{{\phi}^n}{\sqrt{5}} \right], \quad n \geq 0$$

where $\phi = \dfrac{1+\sqrt{5}}{2} \approx 1.6180339887\cdots$ which is the Golden Ratio.

Answer 4

Your sequence is $$a_n=a_{n-1}+a_{n-2},n\geq2,a_0=1,a_1=6$$

Use generating function $$F(x)=\sum_{n=0}^{\infty}a_nx^n=1+6x+\sum_{n=2}^{\infty}a_n=1+6x+\sum_{n=2}^{\infty}a_nx^n=$$ $$=1+6x+\sum_{n=2}^{\infty}a_{n-1}x^n+\sum_{n=2}^{\infty}a_{n-2}x^n=$$ $$=1+6x+x\sum_{n=2}^{\infty}a_{n-1}x^{n-1}+x^2\sum_{n=2}^{\infty}a_{n-2}x^{n-2}$$ we see that$$\sum_{n=2}^{\infty}a_{n-1}x^{n-1}=F(x)-1$$ and $$\sum_{n=2}^{\infty}a_{n-2}x^{n-2}=F(x)$$ from above $$F(x)=1+6x+x(F(x)-1)+x^2F(x)$$ $$F(x)=1+5x+xF(x)+x^2F(x)$$ $$F(x)=\frac{1+5x}{1-x-x^2}$$