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$.
7
votes
1answer
86 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
70 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) ...
20
votes
7answers
662 views
How are we able to calculate specific numbers in the Fibonacci Sequence?
I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...
1
vote
0answers
25 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
2answers
344 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)$ ...
2
votes
2answers
240 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
479 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
108 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
1answer
47 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 ...
2
votes
2answers
37 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 ...
1
vote
2answers
47 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
72 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
92 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
67 views
Fibonacci proof of identity
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
37 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 ...
4
votes
1answer
562 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 ...
3
votes
2answers
63 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
1answer
122 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)$
...
0
votes
0answers
154 views
Fibonacci modular results $3$
The matrix $\begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}$ (inner brackets are the rows)
and its powers with multiplication all elements ($\mod n$) Must be a group.
What the matrix does is to ...
5
votes
1answer
492 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
56 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 ...
4
votes
3answers
337 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
662 views
How to show that this binomial sum satisfies the Fibonacci relation?
The binomial sum
$$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$
satisfies the Fibonacci relation.
I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...
2
votes
4answers
145 views
Explaining a Fibonacci
Explain why the number below is not 299th Fibonacci number:
222232244629420445529739893461909967206666939096499764990979600
I need an explanation
1
vote
3answers
73 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) ...
5
votes
4answers
179 views
The generating function for the Fibonacci numbers
$$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\}$.
Please HELP. Thanks guys.
3
votes
1answer
41 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 ...
1
vote
0answers
29 views
Strange equality of the operator E($Eu_n=u_{n+1}$)
The operator $E$ is defined as $Eu_n=u_{n+1}$.
I encountered a strange equality. when I tried out
Let $u_n$ represent a series such that
$$u_{n+2}=u_{n+1}+u_n. \tag{$\star$}$$
Or
...
1
vote
2answers
72 views
Combinatorics — Fibonacci
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 ...
2
votes
1answer
49 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 ...
2
votes
2answers
49 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
176 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 ...
5
votes
3answers
148 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}
$$
...
5
votes
4answers
232 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 ...
1
vote
1answer
190 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) - ...
1
vote
1answer
39 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 ...
0
votes
2answers
129 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
131 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
96 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 ...
7
votes
7answers
271 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 ...
1
vote
1answer
45 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 ...
3
votes
4answers
74 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
0answers
55 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
0answers
52 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$ ...
2
votes
4answers
187 views
Fibonacci Induction Proof
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 ...
6
votes
1answer
116 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 ...
4
votes
3answers
2k views
Prove this formula for the Fibonacci Sequence
This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n > 1$, where $u_0 = 0$ and $u_1 = 1$.
Show that
...
7
votes
3answers
136 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!!!
2
votes
0answers
82 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
104 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 ...
