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

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

-
Look up solving recurrence relations. You have to solve the recurrence relation: $a_n = a_{n-1} + a_{n-2}$ with initial conditions $a_0 = 1$ and $a_1 = 1$. –  user28877 Oct 30 '13 at 17:58

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.

-

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}$$

-

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.

-
Now I'm curious, is it 570921718804 ? –  Alan Oct 30 '13 at 20:52
I find that $F_{54} = 86267571272$ –  Xoque55 Oct 30 '13 at 21:00
matrixpower[{{1,1},{1,0}},53] = {{139583862445, 86267571272}, {86267571272, 53316291173}} now multiply a11 by 6 and add it to a12, that should be the 54th term of the series. –  Alan Oct 30 '13 at 21:12
570921718804 is the 53rd term of the sequence minus 1. –  Alan Oct 30 '13 at 21:35

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

-