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
1answer
757 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
551 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
101 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
217 views

Explaining a Fibonacci

Explain why the number below is not 299th Fibonacci number: 222232244629420445529739893461909967206666939096499764990979600 I need an explanation
1
vote
3answers
112 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) ...
4
votes
1answer
123 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 ...
4
votes
1answer
279 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 ...
14
votes
1answer
283 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 ...
1
vote
1answer
364 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) - ...
0
votes
1answer
143 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
273 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
175 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
184 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 ...
8
votes
7answers
861 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
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
215 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
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
0answers
164 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$ ...
7
votes
1answer
330 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 ...
3
votes
5answers
299 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.
1
vote
0answers
148 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 ...
21
votes
1answer
356 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 ...
2
votes
2answers
158 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 ...
-2
votes
0answers
189 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 ...
0
votes
2answers
101 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 ...
4
votes
4answers
938 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 ...
4
votes
1answer
101 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
166 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$?
1
vote
1answer
285 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
4answers
144 views

Proving that $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$, where $\alpha$ is the golden ratio

I got stuck on this exercise. It is Theorem 1.15 on page 14 of Robbins' Beginning Number Theory, 2nd edition. Theorem 1.15. $\alpha^{n-2}\leq F_n\leq \alpha^{n-1}$ for all $n\geq 1$. Proof: ...
1
vote
3answers
2k views

nth term in the fibonacci series

I have read in a page that " To find the nth term of the Fibonacci series, we can use Binet's Formula" F(n) = round( (Phi ^ n) / √5 ) provided n ≥ 0 where Phi=1·61803 39887 49894 84820 ...
1
vote
2answers
192 views

Prove $F_{n+1}F_{n-1}-(F_{n})^2=(-1)^n$ without induction

I am asked to pove the statement about fibonacci sequence. The task is from the passage about series and sequences. But the proof seems to need induction way, doesn't it? Prove the statement ...
2
votes
2answers
75 views

Non-isomorphic combinatorial classes with growth rate equal to the golden ratio?

In a couple of weeks, I'm giving a talk about the growth rates of some combinatorial classes. In the introduction, I thought I'd present the class of tilings of a $n\!\times\!2$ strip with dominos, ...
4
votes
3answers
320 views

Why doesn't this induction “proof ”show $f_n = (\phi)^n + (1-\phi)^n$?

Here, $\phi$ is the golden ratio and $f_n$ is the $n^{th}$ Fibonacci number. The formula I'm using is actually the closed form of the Lucas numbers. Let $n = 1$. Then $f_n = 1$ and $\phi + 1 - \phi ...
3
votes
3answers
296 views

Is there a closed form equation for fibonacci(n) modulo m?

Basically I am curious if there's a direct way to calculate fibonacci(n) modulo m with a closed form formula so I don't have to bother with matrix exponentials.
0
votes
1answer
133 views

fibonacci question [duplicate]

Possible Duplicate: Recurrence relation, Fibonacci numbers $(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$. $(i)$ Assume that all $a_n$ are ...
2
votes
1answer
918 views

Recurrence relation, Fibonacci numbers

$(a)$ Consider the recurrence relation $a_{n+2}a_n = a^2 _{n+1} + 2$ with $a_1 = a_2 = 1$. $(i)$ Assume that all $a_n$ are integers. Prove that they are all odd and the integers $a_n$ and $a_{n+1}$ ...
2
votes
2answers
405 views

Fibonacci conjecture: $(F_{n+5})^2 - (F_n)^2 = 3((F_{n+3})^2 - (F_{n+2})^2) + 8 F_{n+2} F_{n+3} $.

So this is the question I have The Fibonacci sequence is a recurrence system given by $$F_1 = 1, \ F_2 = 1, \ F_{n+2} = F_{n+1} + F_n \qquad (n = 1, 2, 3, \ldots).$$ This question concerns the ...
2
votes
1answer
169 views

Another Bijective proof for Fibonacci Identities

I'm going through a past exam, and this question popped up: Prove: $3P_n = P_{n-2} + P_{n+2},\,n>2$ Where $\tilde{P}_j = \{\textrm{monomer-dimer pavings on a } 1\times j \textrm{ board}\}$ and ...
2
votes
1answer
242 views

Bijective Proof of a Fibonacci Identity

Prove (Using bijections): $F_{1}+F_{3}+\cdots+F_{2n-1}=F_{2n}$ Where $F_{i}$ is the $i$th Fibonacci number. Apparently you use monomers and dimers to prove this, but I don't really know what to ...
3
votes
1answer
168 views

Diophantine equation: fermat numbers and fibonacci numbers

My question is how to find all solutions $(m,n)\in\mathbb N^2$ for $F_n=f_m$, where $F_n=2^{2^n}+1$ and $f_m$ is the $m$th fibonacci number: $f_0=0$, $f_1=1$ and $f_n+f_{n+1}=f_{n+2}$ for each ...
4
votes
2answers
119 views

How many ways to reach $1$ from $n$ by doing $/13$ or $-7$?

How many ways to reach $1$ from $n$ by doing $/13$ or $-7$ ? (i.e., where $n$ is the starting value (positive integer) and $/13$ means division by $13$ and $-7$ means subtracting 7)? Let the number ...
1
vote
2answers
361 views

Primitive squareful Fibonacci numbers

In https://oeis.org/A065069 numbers $n$ such that Fibonacci($n$) is not squarefree, but for all proper divisors $k$ of $n$, Fibonacci($k$) is squarefree, are listed. OEIS gives a Mathematica program ...
1
vote
2answers
97 views
2
votes
6answers
271 views

Fibonacci equality, proving it someway

$ F_{2n} = F_n(F_n+2F_{n-1}) $ $ F_n $ is a nth Fibonacci number. I tried by induction but i didn't get anywhere
30
votes
5answers
10k views

Checking if a number is a Fibonacci or not?

The standard way (other than generating up to $N$) is to check if $(5N^2 + 4)$ or $(5N^2 - 4)$ is a perfect square. What is the mathematical logic behind this? Also, is there any other way for ...
0
votes
2answers
130 views

Fibonacci Matrix

I'm looking for a good way to find the matrix form of fibonacci equation, and also a more general implementation. I've looked all other the web and haven't found it. I'll be really thankfull to any ...
2
votes
1answer
230 views

Proof the following proposition: for all $n \geq 0, \mathrm{fib}(n) \leq n!$

I am a comp science undergrad and just started to learn proof. And I have been thinking about this question for a few days. How should I present my answer? Do I have to use the Binet's formula? Or can ...