Questions on the Fibonacci numbers, a special sequence of integers that satisfy the recurrence $F_n=F_{n-1}+F_{n-2}$ with the initial conditions $F_0=0$ and $F_1=1$.

learn more… | top users | synonyms

6
votes
2answers
559 views

Computing nth term of fibonacci-like sequence for large n

Sum up to nth term of fibonacci sequence for very large n can be calculated in O($\log n$) time using the following approach: $$A = \begin{bmatrix} 1&1 \\\\1&0\end{bmatrix}^n$$ ...
0
votes
2answers
130 views

Fibonacci Matrix

I'm looking for a good way to find the matrix form of fibonacci equation, and also a more general implementation. I've looked all other the web and haven't found it. I'll be really thankfull to any ...
2
votes
1answer
230 views

Proof the following proposition: for all $n \geq 0, \mathrm{fib}(n) \leq n!$

I am a comp science undergrad and just started to learn proof. And I have been thinking about this question for a few days. How should I present my answer? Do I have to use the Binet's formula? Or can ...
2
votes
1answer
579 views

Proof about lucas numbers.

Define the Lucas numbers to be $$l_n = l_{n-1} + l_{n-2} $$ if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$. I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by ...
1
vote
2answers
97 views

Existence of 5-d centrally symmetric self-dual polytope

Does there exist a 5-dimensional centrally symmetric self-dual polytope?
1
vote
2answers
114 views

Proof for one of the Lucas problem

Can anybody provide a combinatorial proof or algebraic proof of following identity? $${n\choose 0 }+ {n-1\choose 1}+{n-2\choose 2}+ .. +{{n-\lfloor n/2\rfloor} \choose {\lfloor n/2\rfloor}} = ...
1
vote
1answer
134 views

How to solve for the $n$-th Fibonacci number that is greater than or equal to $N$?

The general formula for the $n$-th Fibonacci number is: $$\frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}$$ where $$\phi = \frac{1 + \sqrt{5}}{2}$$ Given $N$, is there a way to solve for $n$ in this ...
7
votes
2answers
3k views

Every natural number can be written as the sum of distinct Fibonacci numbers?

Can anyone hint me to prove: $\forall n\in \mathbb{N}: \exists$ Fibonacci numbers $ F_{i_1},\ldots,F_{i_k}$ such that: $$\sum F_{i_k}=n$$ Note: Every Fibonacci number can appear only once. Thanks
1
vote
1answer
123 views

Power Variant of Fibonacci sequence

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like ...
1
vote
1answer
242 views

Need formula for sequence related to Lucas/Fibonacci numbers

I am trying to get a formula for the nth term of the following sequence: 2, 14, 22, 58, 266, 398, 1042, 4774, 7142, 18698, 85666, 128158, 335522,... It's not in OEIS and as far as I can tell ...
0
votes
1answer
1k views

How to solve tribonacci series [duplicate]

Possible Duplicate: Fibonacci, tribonacci and other similar sequences Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial ...
0
votes
2answers
228 views

How to reduce the complexity of calculating the following summation? [duplicate]

Possible Duplicate: Summation of series of product of Fibonacci numbers Find $$\sum_{i=1}^{N-1}F_{i + 1} F_{N + 4 - i}$$ Is there a direct formula to calculate this, rather than actually ...
1
vote
1answer
364 views

How to remove the denominator?

I have the following expression for $n>3$: $$\frac{5\cdot(n-1)\cdot[8\cdot\operatorname{Luc}(n) + 5\cdot\operatorname{Luc}(n-1)] + [4\cdot\operatorname{Luc}(n-1) - ...
0
votes
0answers
101 views

Finding the kth n-anacci number

At this wolfram link the formula for the kth n-anacci number is given: http://mathworld.wolfram.com/Fibonaccin-StepNumber.html#eqn8 (Eq. 4) Not sure if I understand correctly. If I want the fifth ...
5
votes
5answers
384 views

Fibonacci nth term

It is known that the nth term of the Fibonacci sequence can be found by the formula: $F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$, where $\phi$ is the golden ratio (1.618...). Would this be the ...
4
votes
1answer
347 views

Summation Of Product Of Fibonacci Numbers

Im trying to find out a general term for the following summation of products of fibonacci numbers:-- $$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$ I tried using Binet's equation but I am ...
4
votes
1answer
442 views

prove that $\operatorname{fib}(n)<{(5/3)}^n$

I am trying to prove that $$ \operatorname{fib}(n)<\left(\frac{5}{3}\right)^n $$ where $\operatorname{fib}(n)$ is the $n^{th}$ fibonacci number. For a proof I used induction, as we know ...
0
votes
1answer
141 views

Reducing this expression to simpler form

$\newcommand{\Fib}{\operatorname{Fib}}$I am trying to reduce this expression for the $n$th term of sequence $G$. $G[n]=\Fib(4) \times \Fib(n-1) + \Fib(5) \times \Fib(n-2) + \Fib(6) \times \Fib(n-3)+ ...
0
votes
2answers
912 views

Summation of series of product of Fibonacci numbers

What is the sum of following product of Fibonacci numbers $$\sum_{k=1}^{n-1} Fib(k)*Fib(n+3-k)$$ can anyone suggest only approach to find general term?
4
votes
1answer
868 views

Sum of product of Fibonacci numbers

I want to calculate the sum of product of Fibonacci number for a given $n$. That is, for given $n$, say $$F_1 F_n + F_2 F_{n-1} + F_3 F_{n-2} + F_4 F_{n-3} + F_5 F_{n-4} + \cdots.$$ what should be ...
2
votes
3answers
1k views

Fibonacci numbers and proof by induction

Consider the Fibonacci numbers $F(0) = 0; F(1)=1; F(n) = F(n-1) + F(n-2)$. Prove by induction that for all $n>0$, $$F(n-1)\cdot F(n+1)- F(n)^2 = (-1)^n$$ I assume $P(n)$ is true and try to show ...
2
votes
0answers
336 views

Fibonacci and Lucas numbers related identities

We know that $H_n$ = $L_n + mF_n$, where $n = 0$ or $n > 0$ is simply relation between Fibonacci sequence and generalized Fibonacci-Lucas sequence. Are there any methods to prove the following ...
5
votes
2answers
253 views

Two sums with Fibonacci numbers

Find closed form formula for sum: $\displaystyle\sum_{n=0}^{+\infty}\sum_{k=0}^{n} \frac{F_{2k}F_{n-k}}{10^n}$ Find closed form formula for sum: $\displaystyle\sum_{k=0}^{n}\frac{F_k}{2^k}$ ...
2
votes
3answers
4k views

What will the recursion tree of Fibonacci series look like?

I am watching the Introduction to algorithm video, and the professor talks about finding a Fibonacci number in $\Theta(n)$ time at point 23.30 mins in the video. How is it $\Theta(n)$ time? Which ...
-2
votes
2answers
431 views

Fibonacci numbers extended

I am so excited and enjoyed the both the proofs of my previous question on Fibonacci series. I am so interested and fascinating person on fib series/functions. I use to do some rough work in my ...
1
vote
2answers
247 views

Fibonacci function

Dear Professors and Mathematcians, Now, I am introducing Fibonacci sequence and function. Consider, $F(x)$ is a Fibonacci function and $f_n$ is Fibonacci sequence. For fixing the initial values by ...
7
votes
2answers
323 views

Fibonacci numbers of the form $5x^2+7$

Numerically I find the positive integer solution of the equation $F_n=5x^2+7$, where $F_n$ denotes the $n^\text{th}$ Fibonacci number, as $(n,x)=(16,14)$ and I guess that the only positive solution of ...
1
vote
2answers
344 views

Fibonacci Sequence Variants

I learnt about finding the $n$th Fibonacci number using matrix exponentiation in $\log n$ time. Then I tried finding similar formula for sequences of the form $$S_{n} = S_{n-1} + S_{n-2} + a n + b$$ ...
4
votes
1answer
285 views

Generating Function of Even Fibonacci

I was posed the following question recently on an exam: Determine the generating function of the even-indexed Fibonacci numbers $F_{2n}$ given that the generating function of Fibonacci numbers is ...
0
votes
1answer
265 views

Fibonacci sequence, strings without 00, and binomial coefficient sums [duplicate]

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that $\displaystyle ...
4
votes
4answers
2k views

Closed form solution of Fibonacci-like sequence

Could someone please tell me the closed form solution of the equation below. $$F(n) = 2F(n-1) + 2F(n-2)$$ $$F(1) = 1$$ $$F(2) = 3$$ Is there any way it can be easily deduced if the closed form ...
0
votes
2answers
284 views

Solving Fibonaccis Term Using Golden Ratio Convergance

While solving this problem, I discovered that there is a relationship between the Fibonacci sequence and the golden ratio. After I got the correct answer via brute force, I discovered this ...
1
vote
1answer
1k views

Smallest Fibonacci number having a common factor with a given number

We have a number $k$ and we have to find the smallest Fibonacci number that has common factor with it(except $1$). We also have $2 \leq k \leq 1,000,000$. The required Fibonacci number is guaranteed ...
0
votes
2answers
205 views

Count the number of paths in the Graph $P_3$. Provide a Proof by Induction using the Fibonacci sequence.

Consider the graph $P_3$ : $n_1$$ \rightarrow$ $n_2$$\rightarrow$ $n_3$$\rightarrow$ $n_4$ we count 6 paths of length k=1, namely: $n_1$ $\rightarrow$ $n_2$ $n_2$ $\rightarrow$ $n_3$ ...
3
votes
2answers
3k views

sum of even-valued and odd-valued Fibonacci numbers

I was solving the Project Euler problem 2 *By starting with 1 and 2, the first 10 terms of Fibonacci Series will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Find the sum of all the even-valued terms ...
2
votes
1answer
146 views

Finding n in Fibonacci closed loop form

The nth term of the Fibonacci series is given by $F_{n}$=$\Big\lfloor\frac{\phi^{n}}{\sqrt{5}}+\frac{1}{2}\Big\rfloor$ How do you get the following expression for n from this? ...
11
votes
5answers
5k views

Why does the Fibonacci Series start with 0, 1?

The Fibonacci Series is based on the principle that the succeeding number is the sum of the previous two numbers. Then how is it logical to start with a 0? Shouldn't it start with 1 directly?
3
votes
1answer
181 views

Fibonacci numbers moduli

I have made some observation on very interesting material on Fibonacci series. I need some help in proving them mathematically. We can observe that the periodicity of Fibonacci numbers modulo m, ...
21
votes
1answer
355 views

The Fibonacci sum $\sum_{n=0}^\infty \frac{1}{F_{2^n}}$ generalized

The evaluation, $$\sum_{n=0}^\infty \frac{1}{F_{2^n}}=\frac{7-\sqrt{5}}{2}=\left(\frac{1-\sqrt{5}}{2}\right)^3+\left(\frac{1+\sqrt{5}}{2}\right)^2$$ was recently asked in a post by Chris here. I ...
10
votes
3answers
263 views

Evaluate the sum: $\sum\limits_{n=0}^{\infty} \frac1{F_{(2^n)}}$

Evaluate the sum: $$\sum_{n=0}^{\infty} \frac{1}{F_{(2^n)}}$$ where $F_{m}$ is the $m$-th term of the Fibonacci sequence. I need some support here. Thanks.
7
votes
1answer
771 views

How to prove that $\mathrm{Fibonacci}(n) \leq n!$, for $n\geq 0$

I am trying to prove it by induction, but I'm stuck $$\mathrm{fib}(0) = 0 < 0! = 1;$$ $$\mathrm{fib}(1) = 1 = 1! = 1;$$ Base case n = 2, $$\mathrm{fib}(2) = 1 < 2! = 2;$$ Inductive case ...
4
votes
1answer
232 views

Golden parallelepiped

Define a golden parallelepiped as a $d$-dimensional box with side lengths $(1, \phi, \phi^2, \ldots, \phi^{d-1})$, where $\phi$ is the golden ratio: ...
6
votes
1answer
279 views

Finding ($2012$th term of the sequence) $\pmod {2012}$

Let $a_n$ be a sequence given by formula: $a_1=1\\a_2=2012\\a_{n+2}=a_{n+1}+a_{n}$ find the value: $a_{2012}\pmod{2012}$ So, in fact, we have to find the value of ...
3
votes
0answers
161 views

Which starting conditions for the Fibonacci sequence, gives most primes

I found the following question (at http://aperiodical.com/2012/05/matt-parkers-twitter-puzzle-25-may/): If you start the Fibonacci sequence 2,1 instead of 1,1 do you get more or fewer primes? ...
4
votes
1answer
344 views

What is the next “Tribonacci-like” pseudoprime?

Given the three roots of $x^3=x^2+x+1$. Then we get the tribonacci-like sequence, $B_n = x_1^n+x_2^n+x_3^n = 3, 1, 3, 7, 11, 21, 39, 71, 131,\dots$ where $B_n = B_{n-1}+B_{n-2}+B_{n-3}$, and the ...
12
votes
1answer
360 views

Why do the Fibonacci numbers recycle these formulas?

The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$ obey the following recurrence relations, $ \begin{aligned} &F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm] &F_{n-1}^3-F_{n}^3-F_{n+1}^3 = ...
5
votes
2answers
638 views

Use of the Reciprocal Fibonacci constant?

The Reciprocal Fibonacci constant ($\psi$) is defined as $$\psi=\sum_{k=1}^{\infty} \frac{1}{F_k}$$ where $F_{k}$ is the $k^{th}$ Fibonacci number. The irrationality of $\psi$ has been proven. ...
0
votes
2answers
477 views

A game: Fibonacci sequences and probability.

Let's play a game. You have two biased coins: coin A has a $0.4$ and $0.6$ for H and T probability and coin B has the opposite ($0.6$ and $0.4$ for H and T). These coins must be flipped one at a time, ...
2
votes
2answers
768 views

Why is fibonacci coding useful?

I have read this wiki article but it seems not very clear to me. Why should we ever use fibonacci coding in data compression if even regular binary coding always gives better results? I mean, it seems ...
6
votes
2answers
192 views

Prove that $\sum\limits_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= \sum\limits_{n=0}^{\infty}\frac{1}{2^{n}}$

I came up with this identity in high school, and I can't remember how I proved it :P Does anyone know how I would go about doing this? $$\sum_{n=0}^{\infty}\frac{F_{n}}{2^{n}}= ...