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
2answers
128 views

Is Fibonacci sequence the minimum of unique pairwise sum sequence?

Let $(a_n)_{n=1}^\infty$ be a strictly increasing (condition added per earlier answer of Amitesh Datta) sequence of natural numbers where all pairwise element sums are unique. Can anyone prove or ...
7
votes
0answers
504 views

A conjecture about Lucas series

Let $L_n$ be the Lucas series: $L_0=2,L_1=1,L_n=L_{n-1}+L_{n-2}(n>1).$ $p$ is a prime number and $p\equiv3,7\pmod {20}$, hence $\exists x,y\in \mathbb Z:2p=x^2+5y^2.$ Is it true that ...
0
votes
3answers
55 views

Fibonacci terms with primal distances

Given any prime $p$, are there fibonacci numbers $F_k $ and $F_n$ such that $|F_n - F_k|=p^i , i \in \mathbb N$?
1
vote
1answer
147 views

Sums and products involving Fibonacci

In summary, if $\phi$ is the golden ratio, I want to show: \begin{align} \sum_{n=1}^\infty \frac1{F_n} &= 4-\phi \\ \sum_{n=1}^\infty \dfrac{(-1)^{n+1}}{F_nF_{n+1}} &= \phi-1 \\ ...
1
vote
1answer
59 views

Solving $ F_{n} = \sum_{i=1}^{n-1} (F_{i}\cdot F_{n-i}) $?

I need to find $F_{n}$ in : $$ F_{n} = \sum_{i=1}^{n-1} (F_{i}\cdot F_{n-i}) , F_0 = 0 , n>=2 $$ This equation screams convolution , I think , but I find it as a quite long solution sometimes. ...
1
vote
3answers
76 views

Find $F_{n}$ in : $F_{n} +2F_{n-1} + … + (n+1)\cdot F_{0} = 3^{n}$

I'm stuck with the question for a while : Find in $$F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} = 3^{n}$$ the element $F_{n}$ . Placing $n-1$ instead on $n$ results in : $$F_{n-1} +2F_{n-2} + ... + ...
2
votes
1answer
78 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...
11
votes
4answers
271 views

Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove $$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$ I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. ...
1
vote
3answers
427 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
2answers
145 views

Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a ...
1
vote
3answers
724 views

Prove that $F(n+3)=2F(n+1)+ F(n)$ for $n \ge 0$

The definition of a Fibonacci number is as follows: $$F(0)=0\\ F(1)=1\\ F(n)= F(n-2)+F(n-1)\text{ for }n\geq 2$$ Prove the given property of the Fibonacci numbers directly from the definition. ...
0
votes
1answer
79 views

Is the Fibonacci number-like function too trivial to investigate about?

To make some interesting recursive function, I generalized Fibonacci numbers to a function $f(x)$ such that satisfies the following condition: Given a function $g(x)$, such that $g(0)=0$ and ...
-1
votes
3answers
1k views

Show that the limit exists and find it's value? [duplicate]

The Fibonacci series defined recursively by $x(1) = 1, x(2) = 2$ and $x(n+1) = x(n) + x(n-1)$ Find$$\lim_{n\rightarrow\infty}\frac{x(n+1)}{x(n)}$$
6
votes
4answers
1k views

Is Binet's formula for the Fibonacci numbers exact?

Is Binet's formula for the Fibonacci numbers exact? $F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$ If so, how, given the irrational numbers in it? Thanks.
6
votes
5answers
298 views

Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive ...
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 ...
0
votes
3answers
677 views

What are the first 3 digits of the product of the first 1000 fibonacci numbers

What are the first 3 digits of the product of the first 1000 Fibonacci numbers? Could anyone give me hints on how to start this problem? I haven't done a problem like this before and I am curious ...
2
votes
1answer
321 views

Seeking a combinatorial proof of the Fibonacci identity $f_{2k-1}f_{4k}=f_{2k}+f_{2k}f_{4k-1}$

I would appreciate if somebody could help me with the following problem Q: Show that (for $k,n\in \mathbb{N}$), if $f_1=f_2=1$, $f_{n+2}=f_{n+1}+f_n$, then ...
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
189 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
139 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
174 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
230 views

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

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 ...
3
votes
1answer
133 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
175 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 ...
7
votes
8answers
985 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 ...
5
votes
5answers
390 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 ...
2
votes
2answers
508 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}$: ...
7
votes
1answer
157 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!} + ...
3
votes
2answers
96 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) ...
2
votes
2answers
717 views

Recurrence for a lagged Fibonacci sequence

I know how to do the matrix for the standard $f(n) = f(n-1) + f(n-2)$ relationship, but what if it's piecewise? For instance, $f(1)$ through $f(30)$ have some preset values, and then for $f(31)$ ...
5
votes
2answers
670 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. ...
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 ...
1
vote
2answers
311 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. ...
2
votes
1answer
199 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
712 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
184 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. ...
7
votes
2answers
194 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
583 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
0answers
82 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 ...
6
votes
1answer
913 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 ...
4
votes
2answers
533 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 ...
2
votes
1answer
788 views

Causal Inverse Z-Transform of Fibonacci

Say the Fibonacci sequence is defined by: $y(n) = y(n-1) + y(n-2)$ initial conditions: $y(0)=0, y(1)=1$ I incorporate those initial conditions as: $y(n) = y(n-1) + y(n-2) + \delta(n-1)$ ...
8
votes
1answer
556 views

N-nacci Identities: The Final Question (Generalizing Time!)

Okay so here is my personal work on the problem set. I only have question 5 remaining which involves generalization of any recursive sequence. $n$'s correspond to the $n$ in n-nacci. I hope to write ...
1
vote
3answers
102 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 ...
8
votes
3answers
1k 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. ...
3
votes
4answers
219 views

Explaining a Fibonacci

Explain why the number below is not 299th Fibonacci number: 222232244629420445529739893461909967206666939096499764990979600 I need an explanation
1
vote
3answers
113 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) ...