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

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
418 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
243 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
322 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
328 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
282 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
255 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
281 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
197 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
145 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
177 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, ...
20
votes
1answer
349 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
261 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
767 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
222 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
276 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
159 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
326 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
351 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
616 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
456 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
738 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
191 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}}= ...
3
votes
1answer
213 views

If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$.

Edit: The $F$'s are Fibonacci numbers. I need an idea on how to show the following: If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. I believe that using the fact that ...
4
votes
5answers
592 views

Showing that $f_{2n+1}=f_{n+1}^2+f_n^2$.

I am trying to solve the following exercise: Let $f_1=1$, $f_2=1$, $f_{n+1}=f_n+f_{n-1}$, where $n\in\mathbb{N}$. Show that $f_{2n+1}=f_{n+1}^2+f_n^2$. I have not had much progress, but this is ...
2
votes
2answers
632 views

Using linear algebra, how is the Binet formula (for finding the nth Fibonacci number) derived?

If possible, please refrain from any type of proof besides linear algebra. So, using the recursion formula $F_{n+1} = F_{n-1} + F_n$, for $n\gt 1$, and where $F_0 = 0$ and $F_1 = 1$, and the Fibonacci ...
1
vote
0answers
86 views

Lucas numbers theory confused [duplicate]

Possible Duplicate: Prove this formula for the Fibonacci Sequence How does one find a formula for the recurrence relation $a_{1}=1,a_{2}=3, a_{n+2}=a_{n+1}+a_{n}?$ How do I go about ...
3
votes
3answers
321 views

Another way to go about proving Binet's Formula

As I showed in another question of mine, it is easy to prove that $$\tag{1}\phi^{n+1} =F_{n+1} \phi+F_{n }$$ given $F_1=1$ , $F_2=1$ , $F_{n+1}=F_n+F_{n-1}\text{ ; }n\geq2$. Now, extending $(1)$ ...
7
votes
3answers
690 views

How to prove that $\lim \limits_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}$

How would one prove that $$\lim_{n\rightarrow \infty} \frac{F_{n+1}}{F_n}=\frac{\sqrt{5}+1}{2}=\varphi$$ where $F_n$ is the nth Fibonacci number and $\varphi$ is the Golden Ratio?
5
votes
1answer
465 views

(Long) Fibonacci Sequence Question

I am working on a rather long question. I am going to write out the question, and what I've come up with so far. I'm not sure if the question has too many parts to receive answers but I will ...
8
votes
4answers
20k views

What do Subscripted numbers in an equation mean?

$F_n= F_{n-1}+ F_{n - 2}$ I know that when a number is superscripted it means "to the power of", but what does the subscript mean?
1
vote
1answer
130 views

“Non-commutative” Recurrence relation $ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2} $

I have a problem, which is probably quite trivial. Consider a recurrence relation of the form $$ C_m = \alpha_m C_{m-1} + \beta_m C_{m-2}, $$ where the coefficients $\alpha_m$ and $\beta_m$ are ...
11
votes
3answers
710 views

Infinite Series: Fibonacci/ $2^n$

I presented the following problem to some of my students recently (from Senior Mathematical Challenge- edited by Gardiner) In the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... each term ...
6
votes
4answers
2k views

Fibonacci's final digits cycle every 60 numbers

How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60? References: The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The ...
6
votes
3answers
213 views

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; I was stuck with this question for a while... Help me please!!! Thanks!!!
3
votes
2answers
132 views

Binet's Formula. An operational approach.

I read quite a while ago this proof of Binet's formula. ( I am not 100% sure this is the way it was presented, but it gives an idea. I'm not approving of this method or saying it is correct.) Let ...
7
votes
2answers
303 views

Fibonacci numbers with largest prime factor appearing more than once

$F_6=2^3$ and $F_{12}=2^43^2$. Is there an $n>12$ such that $F_n=p^2k$ with $p$ prime and $k$ is $p$-smooth?
7
votes
1answer
722 views

Another way to go about proving the limit of Fibonacci's sequence quotient.

It is not difficult to inductively prove that $$\eqalign{ & \phi = \phi + 0 \cr & {\phi ^2} = \phi + 1 \cr & {\phi ^3} = 2\phi + 1 \cr & {\phi ^4} = 3\phi + 2 ...
8
votes
3answers
179 views

How can I show that $\sum\limits_{n=1}^\infty \frac{z^{2^n}}{1-z^{2^{n+1}}}$ is algebraic?

Show that $$\sum_{n=1}^\infty \frac{z^{2^n}}{1-z^{2^{n+1}}}$$ is algebraic. More specifically, solve this and get exact values. Then use the result to evaluate $$\sum_{n=0}^\infty ...
31
votes
3answers
683 views

Very curious properties of ordered partitions relating to Fibonacci numbers

I came across some interesting propositions in some calculations I did and I was wondering if someone would be so kind as to provide some explanations of these phenomenon. We call an ordered ...
8
votes
3answers
987 views

Prove by induction Fibonacci equality

[question:] Prove by induction that the i th Fibonacci number satisfies the equality $$F_i=\frac{\phi^i-\hat{\phi^i}}{\sqrt5}$$where $\phi$ is the golden ratio and $\hat{\phi}$ is its conjugate. ...
14
votes
2answers
315 views

Generalized Fibonacci Sequence Question

The Fibonacci Sequence is defined as the recurrence $a(n)=a_{n-1}+a_{n-2}$ where $a(0)=0$ and $a(1)=1$. Today, I was bored so I considered the sequence $a(n)=\sqrt{a_{n-1}}+\sqrt{a_{n-2}}$. Ten ...
7
votes
8answers
965 views

Need help deriving recurrence relation for even-valued Fibonacci numbers.

That would be every third Fibonacci number, e.g. $0, 2, 8, 34, 144, 610, 2584, 10946,...$ Empirically one can check that: $a(n) = 4a(n-1) + a(n-2)$ where $a(-1) = 2, a(0) = 0$. If $f(n)$ is ...
4
votes
1answer
533 views

Why Fibonacci numbers are too often found on nature?

Fibonacci number has something to do with natural growth. Though the function is very straight forward, we see this in nature. Does nature follow the function or its the simplified model of the ...
1
vote
4answers
281 views

Generalized Fibonacci sequences

Why Fibonacci sequence start at $0$, Tribonacci sequence with $0,0$, Tetranacci with $0,0,0$, etc. [ref OEIS] Has any good reasons for that? These sequences arise in generalization of Pascal Triangle ...