Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
    
There is a free book online about this stuff by Herbert Wilf. Google for it. –  ncmathsadist Oct 30 '13 at 18:04
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.