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$.
3
votes
2answers
69 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
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 ...
1
vote
1answer
46 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
36 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
44 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 ...
7
votes
0answers
62 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
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
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 ...
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
175 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
4answers
230 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
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 ...
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}
$$
...
0
votes
2answers
128 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
95 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
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
73 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
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
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
186 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 ...
7
votes
7answers
270 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 ...
2
votes
0answers
81 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 ...
1
vote
1answer
94 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
81 views
Fibonnaci 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
63 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 ...
4
votes
4answers
190 views
Fibonacci Proof
Prove that: $$F_1F_2+F_2F_3+F_3F_4+\cdots+F_{2n-1}F_{2n}=F_{2n}^2$$
I set it up so:
$$F^2(2k) + F(2k+1)F(2k+2) = F^2(2k+2)$$
I've tried:
$$F(2k)^2 + F(2k+1)*F(2k+2) = ...
2
votes
2answers
101 views
Proof That the Ratio of Sucessive N-nacci Numbers Tends to 2.
For the paper that I'm working on involving N-nacci Recursion Formulas I need to prove that $$ \lim_ {n \to \infty}\lim_{a \to \infty} \left | \frac{f^{(n)}_{a+1}}{f^{(n)}_a} \right | = 2$$
To start ...
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 ...
0
votes
2answers
77 views
Finding $a \bmod b$ where $a,b$ are large Fibonacci numbers
For moderately large values of $b$ we can use Chinese Remainder Theorem, by factorizing $b$. But for very large values of $b$, (for example $b$ is the 1000th Fibonacci number) factorization will take ...
3
votes
4answers
319 views
Fibonacci( Binet's Formula Derivation)-Revised with work shown
Okay so here is the revised question with my current work.
Links to previous post(s)(Just for Gerry): Fibonacci Numbers - Complex Analysis
Here's my attempt on the problem set thus far: (Note ...
-2
votes
0answers
166 views
Fibonacci Numbers - Complex Analysis [duplicate]
Possible Duplicate:
Complex Analysis - Integral over a circle of radius R
Hey guys~ Does anyone know where to find the solutions to this problem set on page 106 involving the fibonacci ...
3
votes
1answer
78 views
Convergence of $\sum_{n=1}^{\infty}(-1)^n\frac{n}{f_n}$ where $f_n$ is the $n$'th Fibonacci number
Can we show convergence of$$B=\sum_{n=1}^{\infty}(-1)^n\frac{n}{f_n}$$where $f_n$ is the $n$'th Fibonacci number?
And then can we determine the exact value of $B$?
4
votes
2answers
119 views
$n +1$th Fibonacci number modulo $n$
The Pisano period studies the $n$th Fibonacci number $F_{n}$ modulo $n$. Is there anything about $F_{n + 1} \pmod n$?
4
votes
1answer
79 views
Fibonnaci Sequence and series limits
1) Let $F_1 = 1$, $F_2 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$.
How do you prove that
$$\sum_{n=2}^\infty \frac1{F_{n-1} F_{n+1}} = 1$$
$$\sum_{n=2}^\infty \frac{F_n}{F_{n-1} F_{n+1}} ...
1
vote
1answer
122 views
Fibonacci Generating Function of a Complex Variable
So I'm doing work on the Fibonacci Numbers, and I came across this problem for the generating function
for the recursive fibonacci numbers.
I have two questions:
1. Why is it useful to use a ...
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)$
...
