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
0answers
188 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
924 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 ...
3
votes
1answer
100 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
277 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
143 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
189 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
309 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 ...
2
votes
3answers
313 views

Lucas Numbers and Matrices

Is there a $2 \times 2$ matrix that can be raised to any power to obtain the Lucas Numbers? If so, what is that matrix? I've looked around on this website and other sites and am not able to find the ...
0
votes
1answer
214 views

recurrence and fibonacci [closed]

could someone possibly help me with a proof. prove $a_n = F_{2n-1}$ for fibonacci numbers and a recurrence relation where $a_1 = 1$ $a_2 = 2$ $a_3 = 5$ $a_4 = 13$ $a_5 = 34$ 89,233,610,1597 ...
3
votes
3answers
292 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
131 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
909 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
390 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
166 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
231 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
166 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
118 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
352 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 ...
4
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 proof it ? Can you help me ? Let $f_n$ be Fibonacci Sequence. ...
1
vote
2answers
94 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
29
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
129 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 ...
2
votes
1answer
566 views

Proof about lucas numbers.

Define the lucas numbers to be $$l_n = l_{n-1} + l_{n-2} $$ if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$ I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by ...
1
vote
2answers
114 views

Proof for one of the Lucas problem

Can anybody provide a combinatorial proof or algebraic proof of following identity? $${n\choose 0 }+ {n-1\choose 1}+{n-2\choose 2}+ .. +{{n-\lfloor n/2\rfloor} \choose {\lfloor n/2\rfloor}} = ...
1
vote
1answer
134 views

How to solve for the $n$-th Fibonacci number that is greater than or equal to $N$?

The general formula for the $n$-th Fibonacci number is: $$\frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}$$ where $$\phi = \frac{1 + \sqrt{5}}{2}$$ Given $N$, is there a way to solve for $n$ in this ...
4
votes
1answer
282 views

Generating Function of Even Fibonacci

I was posed the following question recently on an exam: Determine the generating function of the even-indexed Fibonacci numbers $F_{2n}$ given that the generating function of Fibonacci numbers is ...
7
votes
2answers
3k views

Every natural number can be written as the sum of distinct Fibonacci numbers?

Can anyone hint me to prove: $\forall n\in \mathbb{N}: \exists$ Fibonacci numbers $ F_{i_1},\ldots,F_{i_k}$ such that: $$\sum F_{i_k}=n$$ Note: Every Fibonacci number can appear only once. Thanks
1
vote
1answer
122 views

Power Variant of Fibonacci sequence

I was trying to simplify the following sequence, such that I can calculate the $n$th term in $\log n$ time. This can be done, if we can express the $n$th in terms of combinations of Fibonacci like ...
1
vote
1answer
239 views

Need formula for sequence related to Lucas/Fibonacci numbers

I am trying to get a formula for the nth term of the following sequence: 2, 14, 22, 58, 266, 398, 1042, 4774, 7142, 18698, 85666, 128158, 335522,... It's not in OEIS and as far as I can tell ...
0
votes
2answers
226 views

How to reduce the complexity of calculating the following summation? [duplicate]

Possible Duplicate: Summation of series of product of Fibonacci numbers Find $$\sum_{i=1}^{N-1}F_{i + 1} F_{N + 4 - i}$$ Is there a direct formula to calculate this, rather than actually ...
4
votes
1answer
347 views

Summation Of Product Of Fibonacci Numbers

Im trying to find out a general term for the following summation of products of fibonacci numbers:-- $$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$ I tried using Binet's equation but I am ...
0
votes
1answer
1k views

How to solve tribonacci series [duplicate]

Possible Duplicate: Fibonacci, tribonacci and other similar sequences Suppose my Tribonacci series is like this: \begin{equation} T(n) = T(n-1) + T(n-2) +T(n-3) \end{equation} with initial ...
0
votes
0answers
101 views

Finding the kth n-anacci number

At this wolfram link the formula for the kth n-anacci number is given: http://mathworld.wolfram.com/Fibonaccin-StepNumber.html#eqn8 (Eq. 4) Not sure if I understand correctly. If I want the fifth ...
4
votes
1answer
435 views

prove that $\operatorname{fib}(n)<{(5/3)}^n$

I am trying to prove that $$ \operatorname{fib}(n)<\left(\frac{5}{3}\right)^n $$ where $\operatorname{fib}(n)$ is the $n^{th}$ fibonacci number. For a proof I used induction, as we know ...
0
votes
1answer
141 views

Reducing this expression to simpler form

$\newcommand{\Fib}{\operatorname{Fib}}$I am trying to reduce this expression for the $n$th term of sequence $G$. $G[n]=\Fib(4) \times \Fib(n-1) + \Fib(5) \times \Fib(n-2) + \Fib(6) \times \Fib(n-3)+ ...
1
vote
0answers
318 views

Fibonacci and Lucas relations

We know that $H_n$ = $L_n + mF_n$, where $n = 0$ or $n > 0$ is simply relation between Fibonacci sequence and generalized Fibonacci-Lucas sequence. Are there any methods to prove the following ...
2
votes
3answers
4k views

What will the recursion tree of Fibonacci series look like?

I am watching the Introduction to algorithm video, and the professor talks about finding a Fibonacci number in $\Theta(n)$ time at point 23.30 mins in the video. How is it $\Theta(n)$ time? Which ...
-2
votes
2answers
420 views

Fibonacci numbers extended

I am so excited and enjoyed the both the proofs of my previous question on Fibonacci series. I am so interested and fascinating person on fib series/functions. I use to do some rough work in my ...
7
votes
2answers
323 views

Fibonacci numbers of the form $5x^2+7$

Numerically I find the positive integer solution of the equation $F_n=5x^2+7$, where $F_n$ denotes the $n^\text{th}$ Fibonacci number, as $(n,x)=(16,14)$ and I guess that the only positive solution of ...
1
vote
2answers
243 views

Fibonacci function

Dear Professors and Mathematcians, Now, I am introducing Fibonacci sequence and function. Consider, $F(x)$ is a Fibonacci function and $f_n$ is Fibonacci sequence. For fixing the initial values by ...
1
vote
2answers
328 views

Fibonacci Sequence Variants

I learnt about finding the $n$th Fibonacci number using matrix exponentiation in $\log n$ time. Then I tried finding similar formula for sequences of the form $$S_{n} = S_{n-1} + S_{n-2} + a n + b$$ ...
10
votes
3answers
262 views

Evaluate the sum: $\sum\limits_{n=0}^{\infty} \frac1{F_{(2^n)}}$

Evaluate the sum: $$\sum_{n=0}^{\infty} \frac{1}{F_{(2^n)}}$$ where $F_{m}$ is the $m$-th term of the Fibonacci sequence. I need some support here. Thanks.
8
votes
3answers
179 views

How can I show that $\sum\limits_{n=1}^\infty \frac{z^{2^n}}{1-z^{2^{n+1}}}$ is algebraic?

Show that $$\sum_{n=1}^\infty \frac{z^{2^n}}{1-z^{2^{n+1}}}$$ is algebraic. More specifically, solve this and get exact values. Then use the result to evaluate $$\sum_{n=0}^\infty ...
0
votes
1answer
257 views

Fibonacci sequence, strings without 00, and binomial coefficient sums [duplicate]

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that $\displaystyle ...