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

2
votes
5answers
2k views

What is the summation notation for the Fibonacci numbers?

I learned about summation notation the other day, and I'm looking for a way to write the Fibonacci numbers with it. What would it look like?
0
votes
3answers
95 views

Fiddling with a Fibonacci-Like Sequence

Let $X\in\mathbb{Z}.$ Let $F_n$ be a sequence of positive integers given by $$F_{i+1}=F_i+F_{i-1}$$ $$F_2=X*F_1+F_0$$ I am trying to find an upper bound or (sharp) inequality of $F_i$ in terms of ...
7
votes
2answers
129 views

Error in Fibonacci recurrence proof by induction?

I'm working on a problem from a number theory book (Number Theory by George E. Andrews - problem 1-1-11). The text reads: Prove: $\displaystyle F_1F_2+F_2F_3+F_3F_4+\ldots+F_{2n-1}F_{2n}=F_{2n}^2$ ...
6
votes
3answers
163 views

Fibonacci sequence: how to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$?

Let $F_n$ be the $n$th Fibonacci number. Let $\alpha = \frac{1+\sqrt5}2$ and $\beta =\frac{1-\sqrt5}2$. How to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$? I'm completely stuck on this question. ...
3
votes
1answer
133 views

Have I correctly derived an inverse to the Binet formula?

I was interested by another user's question on finding such an inverse and in particular noted Will Orrick's comment in the best answer that one can square both sides to obtain a quartic.I thought I'd ...
3
votes
1answer
163 views

Important numbers in Combinatorics

I recently went through some important numbers like the Stirling and Bell number for calculation of partitions /equivalence relations. I was wondering if someone can help me get a list of important ...
3
votes
1answer
127 views

Invent a combinatorial interpretation for the ''Tribonacci numbers''

" Recall that our combinatorial interpretation of the Fibonacci numbers $f_0 = f_1 = 1$ with $f_n = f_{n-1} + f_{n-2}$ for $n \geq 2$ was the number of ways to tile a board of length $n$ using squares ...
2
votes
3answers
112 views

How to prove? (Do not use mathematical induction)

I would appreciate if somebody could help me with the following problem: Q: Show that $$f_1=f_2=1, f_{n+2}=f_{n+1}+f_{n}(n\in \mathbb{N})~~~~ \Rightarrow ...
0
votes
2answers
168 views

intuition for the closed form of the fibonacci sequence

I'm trying to picture this closed form from Wikipedia visually: The idea is, if you take $\phi^n / \sqrt{5}$ and round it to the nearest integer, you'll get the $n$th Fibonacci number. I see ...
2
votes
2answers
480 views

How do I prove Binet's Formula? [duplicate]

My initial prompt is as follows: For $F_{0}=1$, $F_{1}=1$, and for $n\geq 1$, $F_{n+1}=F_{n}+F_{n-1}$. Prove for all $n\in \mathbb{N}$: ...
3
votes
2answers
95 views

What is the functional inverse (with respect to $h$ (!)) of $f^{\circ h}(x)={F(h) +x F(h-1) \over F(1+h) +x F(h) }$?

I've considered the fractional iteration of $f(x) = {1 \over 1+x} $ for which the general expression depending on the iteration-height parameter $h$ might be assumed by the formula $$ f^{\circ h}(x) ...
1
vote
1answer
74 views

What is the broader name for fibonacci and lucas sequences?

Fibonacci and Lucas sequences are very similar in their definition. However, I could just as easily make another series with a similar definition; an example would be: $$x_0 = 53$$ $$x_1 = 62$$ $$x_n ...
2
votes
1answer
188 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
1
vote
2answers
663 views

proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3

I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers: $$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
2
votes
2answers
171 views

Induction on the Fibonacci sequence?

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. ...
1
vote
1answer
94 views

Prove relation between Lucas and Fibonacci numbers using tilings

I struggle a lot with combinatorial proofs and was hoping for some help. I need to prove by strong induction that $L_n = F_{n-2} + F_n$ and how this shows that $L_n$ counts the tilings of the circular ...
7
votes
2answers
183 views

Fiboncacci theorem: Proof by induction

I have the following theorem to prove by induction: $$ F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$ It is mentioned in my script that the proof should be possible only by using the ...
2
votes
2answers
511 views

How can I find an inverse to the Binet formula?

I'm already aware of the Binet formula $F_n = \frac{\varphi^n + \frac{1}{\varphi^n}}{\sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of ...
1
vote
3answers
393 views

Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers

I'm lost on where to start on this proof: Using the fact that $A^m A^n = A^{m+n}$ , prove the identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ I want to use induction starting with n = 1, but would ...
1
vote
0answers
80 views

Simplify Fibonacci Power Series

I am working on an algorithm to count the number of models for Exactly One in Three SAT (X3SAT) instances. It is known that a chain of X3SAT clauses of length $c$ has $F(c+3)$ satisfying assignments ...
7
votes
1answer
151 views

Identity for $e$ in terms of the Fibonacci sequence.

The following identity appears in Martin Gardner's paper, "Dr. Matrix on Little Known Fibonacci Curiosities: $$e = \frac{1 + 1 + \frac{2}{2!} + \frac{3}{3!} + \frac{5}{4!} + \frac{8}{5!} + ...
4
votes
2answers
488 views

Computing first digits of Fibonacci numbers

How would you compute the first $k$ digits of the first $n$th Fibonacci numbers (say, calculate the first 10 digits of the first 10000 Fibonacci numbers) without computing (storing) the whole numbers ...
1
vote
3answers
100 views

Fibonacci series in 0-Even-Odd-Even-Odd-N series up to N

Another question from the test for the Normale of Pisa: Consider the series $S_n$ of integer numbers repeteandly even - odd - even - odd that start with 0 and finish with n, so with n = 3 we get 2 ...
1
vote
3answers
111 views

Fibonacci and the algebraic expression $x^2-x-1$

$$\left( \left( 1/2\,{\frac {-\beta+ \sqrt{{\beta}^{2}-4\,\delta\, \alpha}}{\alpha}} \right) ^{i}- \left( -1/2\,{\frac {\beta+ \sqrt{{ \beta}^{2}-4\,\delta\,\alpha}}{\alpha}} \right) ^{i} \right) ...
16
votes
4answers
7k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$.
4
votes
1answer
121 views

Fibonacci Coding - Error detection/correction

I'm researching into Fibonacci coding and up until this point I have surprised myself and understood the majority of what I have been reading. I'm now looking into the usefulness of Fibonacci ...
3
votes
3answers
187 views

Combinatorics — Fibonacci: formula for $F_1+F_3+ \cdots +F_{2n+1} $

For the following expression, find a simple formula which only involves one Fibonacci number. Then prove it by induction. $$F_1+F_3+ \cdots +F_{2n+1} $$ I'm be appreciated for any help. I have no ...
4
votes
1answer
278 views

Number of Permutations Fixed by the Fundamental Transformation is Fibonacci

Writing a permutation in $S_n$ as a product of disjoint cycles, we define a standard representation by writing each cycle with its largest element first, and ordering the cycles by the increasing ...
3
votes
3answers
173 views

“Fat” sets of integers and Fibonacci numbers

Let us call a set of integers "fat" if each of its elements is at least as large as its cardinality. For example, the set $\{10,4,5\}$ is fat, $\{1,562,13,2\}$ is not. Define $f(n)$ to count the ...
14
votes
1answer
282 views

Fibonacci Sequence in $\mathbb Z_n$.

Consider a Fibonacci sequence, except in $\mathbb Z_n$ instead of $\mathbb Z$: $$F(1) = F(2) = 1$$ $$F(n+2) = F(n+1) + F(n)$$ It is easy to see that each of these sequences must cycle through some ...
6
votes
4answers
716 views

Fibonacci identity proof

I've been struggled for this identity for a while, how can I use combinatorial proof to prove the Fibonacci identity $$F_2+F_5+\dots+F_{3n-1}=\frac{F_{3n+1}-1}{2}$$ I know that $F_n$ is number of ...
0
votes
1answer
138 views

quick approximation for largest fibonacci under a limit?

I asked in a previous post about finding a closed form for: $$\sum_{i=0}^{n}F_{3i}$$ which is the sum of the even fibs less than or equal to the nth even fib. the great answersI got showed me a very ...
5
votes
3answers
452 views

Closed form for the sum of even fibonacci numbers?

I recently took a look a project euler, and I am trying to think of a smart way to do number 2. I looked at the sequence, and I saw that the question is basically asking for $$ \sum_{i=1}^n F_{3i} $$ ...
0
votes
2answers
271 views

Verify the following identity for Fibonacci numbers

This is a homework problem that I would very much appreciate some help with. Thanks!
5
votes
3answers
174 views

Summation of Fibonacci numbers.

Let $f_n$ be the sequence of Fibonacci numbers. We need to show that $$\sum_{n\ge0} f_n x^n = \dfrac{1}{1-x-x^2}$$ I remember a solution when we are using the generating functions like: $f(x) = F_0 ...
1
vote
4answers
179 views

Fibonacci sequence

Given an integer $n ≥ 1$, let $f_n$ be the number of lists whose elements all equal $1$ or $2$ and add up to $n−1$. For example $f_1 = 1 = f_2$ because only the empty list ($0$ ones and $0$ twos) sums ...
1
vote
1answer
57 views

All sequences constructed by using the denominator as nominator and the sum of denominator and nominator as denominator converges to $\phi-1$

Assume we are given any number a. Write it in the form $a = \frac{b}{c}$ (if rational, in the usual way, if irrational, use forms like $\frac{a}{1}$). Construct a sequence ...
4
votes
4answers
213 views

Profinite and p-adic interpolation of Fibonacci numbers

On the topic of profinite integers $\hat{\bf Z}$ and Fibonacci numbers $F_n$, Lenstra says (here & here) For each profinite integer $s$, one can in a natural way define the $s$th Fibonacci ...
1
vote
2answers
280 views

How to vary increase of x as n increments through the Fibonacci series?

Excuse my incorrect use of terminology, I hope my question is clear: I am coding a Python module which tests whether a given number is a member of the Fibonacci series. No problem with that. ...
1
vote
0answers
69 views

combinatorial proof of Fibonacci identities [duplicate]

Give a combinatorial proof to each of the Fibonacci identities: $$nF_0+(n-1)F_1+\dots\dots+2F_{n-2}+F_{n-1}=F_{n+3}-(n+2)$$ and $$ F_2+F_5+\dots\dots+F_{3n+1}=\frac{F_{3n+1}-1}{2} $$ Assume that ...
1
vote
2answers
111 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
1
vote
0answers
163 views

Is this “Elegant” algorithm for logarithm by Zeckendorf representation, the same as an 'efficient' algorithm?

The algorithm here which computes the exponent $b$ given a base $a$, and given $n$ = $a$^$b$, appears no better to me than simply counting the number of times we divide $n$ through by the base $a$ ...
5
votes
4answers
3k views

Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares

Using induction, how can I show the following identity about the fibonacci numbers? I'm having trouble with simplification when doing the induction step. Identity: $$f_n^2 + f_{n+1}^2 = f_{2n+1}$$ I ...
7
votes
1answer
325 views

Fibonacci numbers that are powers?

The Fibonacci sequence is: $$\left(f_n\right) = \left(0,1,1,2,3,5,8,13,21,34,55,89,144,\dots\right)$$ where we start with $0$ and $1$ and each term in the sequence is the sum of the two previous ...
8
votes
7answers
842 views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
6
votes
1answer
732 views

Finding the binary representation of the $n$th Fibonacci term

Objective: To find the binary representation ( or no. of 1's in binary representation) of nth term in Fibonacci sequence where n is of the order 10^6. My current approach: Find nth term (in decimal) ...
3
votes
5answers
296 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
1
vote
1answer
149 views

Some proof question about Fibonacci sequence

The Fibonacci sequence as $f(n)$ (1) show that $f(n) \le (\frac{7}{4})^n$, for all$ n \ge 0$ (2) show that $f(n) \ge \frac{1}{3}(\frac{3}{2})^n$, for all $ n \ge 1$ thanks.
3
votes
2answers
217 views

Another Fibonacci identity

Here's a problem that is leading me in circles. Consider the Fibonacci number $F_n$ defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for all $n \geq 2$. Prove that $F_{2n-1} = F_{n}^2 ...
1
vote
0answers
144 views

The zeta-function of Fibonacci sequence?

I have been told that, for a given sequence ${N_r}$, its zeta-function is given by $exp(\Sigma _{r=1}^{\infty} N_rT^r/r)$. Since I have barely any experience with such a sum, I tried to find some ...