Is there any general formula for fibonacci(A+B)?

I have tried to derive it , and got following results. $$\begin{align} &fib(a+1)=1*fib(a)+fib(a-1)\\ &fib(a+2)=2*fib(a)+fib(a-1)\\ &fib(a+3)=fib(a+2)+fib(a+1)=\!\text{(sum of above two formulas)}\!=3fib(a)+2fib(a-1)\\ &fib(a+4)=5fib(a)+3fib(a-1)\\ &\qquad\vdots\\ &fib(a+b)=fib(b+1)*fib(a)+fib(b)*fib(a-1) \end{align}$$

Is this formula correct or there is something wrong..?

  • 2
    $\begingroup$ This is correct! You may want to peruse Wikipedia's Fibonacci page, because they have this and more: en.wikipedia.org/wiki/Fibonacci_number $\endgroup$ – Matt Groff Apr 6 '16 at 15:58
  • $\begingroup$ this appears to be related to an active competition, codechef.com/APRIL16/problems/FIBQ . I note that one of your prior questions was locked because it, too, was from a codechef competition (math.stackexchange.com/questions/1686737/…). $\endgroup$ – lulu Apr 6 '16 at 16:09
  • $\begingroup$ @lulu .! I am learning about properties of fibonacci numbers. Main motive of long contest is learning , you can learn lot of things . I didnot ask direct answer for that question . I just wanted to know that whatever i am doing is correct or not ...! $\endgroup$ – Winchester Allpesh Apr 6 '16 at 16:55
  • 1
    $\begingroup$ Your prior question was exactly equivalent to a (then active) codechef competition problem. In neither case did you cite the contest as the source for your question. Most people here would, I think, want to hold off on answering until the competition was done. At a minimum, you should link to the ongoing contest so people can decide for themselves if they want to help. $\endgroup$ – lulu Apr 6 '16 at 17:04

This follows from the matrix formulation, which is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Let $ A=\begin{pmatrix}1&1\\1&0\end{pmatrix} $. Then $A^{a+b}=A^{a}A^b$. Just read the corresponding entries.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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