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

5
votes
3answers
182 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
193 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
58 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
226 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
318 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
118 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
173 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 ...
8
votes
1answer
358 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
925 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
861 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
322 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
152 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
232 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
160 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 ...
5
votes
5answers
287 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) = ...
7
votes
1answer
330 views

Irrationality of reciprocal Fibonacci constant

I read that it was proved that reciprocal Fibonacci constant $$\sum_{n} \frac{1}{F_n} = \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{8} + \frac{1}{13} + \frac{1}{21} ...
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 ...
8
votes
1answer
557 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
103 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
972 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
190 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 ...
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
168 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
162 views

Fibonacci 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
304 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 ...
2
votes
1answer
800 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
2answers
109 views

number theory fibonacci

Using facts of the Fibonacci sequence, I need to show that if $m,n$ are natural numbers that satisfy $m \mid F_n$ and $m \mid F_{n+1}$, then $m=1$. I am not sure where to start with this.. I am ...
1
vote
4answers
145 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 ...
3
votes
2answers
466 views

Fibonacci / Lucas Numbers Relationship: $F_{2n} = F_n L_n$

Prove the identity by induction: $$ F_{2n} = F_n L_n, $$ where $F_n$ and $L_n$ are the $n^{th}$ Fibonacci and Lucas number, respectively. I have an answer but am not happy with it since it doesn't ...
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 ...
7
votes
3answers
603 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
2
votes
2answers
80 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
342 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
2answers
762 views

Induction Proof: Formula for Fibonacci Numbers as Odd and Even Piecewise Function

How can we prove by induction the following? $ F_{n+1} = \left\{ \begin{array}{l l} F_{n/2}^2+F_{(n+2)/2}^2 & \quad \text{if $n$ is even}\\ ...
4
votes
1answer
2k views

Induction Proof: Formula for Sum of n Fibonacci Numbers

I am stuck though on the way to prove this statement of fibonacci numbers by induction : my steps: definition: $F_{0}:=0, F_{1}:=1 $ and $F_{n}:=F_{n-1}+F_{n-2}$ The Hypothesis is: $\sum_{i=0}^{n} ...
3
votes
3answers
309 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
136 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 ...
1
vote
1answer
104 views

What does $F^2_n$ mean?

In this Wikipedia entry on Cassini's identity, I saw this equation: $F_{n-1}F_{n+1}-F^2_n=(-1)^n$ $F^2_n$, what does that mean? Is it a summation signs for n to 2? I don't know what it means.
2
votes
1answer
942 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
458 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
171 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
250 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 ...
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 ...
3
votes
1answer
173 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 ...
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
2answers
386 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 ...
5
votes
4answers
3k views

How to prove gcd of consecutive Fibonacci numbers is 1? [duplicate]

Possible Duplicate: Prove that two any consecutive terms of Fibonacci sequence are relatively prime How to prove it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...