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

22
votes
3answers
835 views

Why does $\frac{1 }{ 99989999}$ generate the Fibonacci sequence?

$\frac{1}{99989999} = 1.00010002000300050008001300210034005500890144... \times 10^{-8}$ (Link), which includes the Fibonacci sequence $(1\ 1\ 2\ 3\ 5\ 8\ 13\ 21\ 55\ 89\ 144\ldots )$. This is ...
0
votes
0answers
47 views

Fibonacci series generated with division $1/999999999999999999999998999999999999999999999999$ [duplicate]

I tested the suggestion of finding the Fibonacci series by division, which sounded very surprising to me. I therefore used a simple sympy script to test it and found that it works as advertised. ...
4
votes
0answers
28 views

The $q$-continued fraction for tribonacci constant and others

Let $q = e^{-2\pi}$. We are familiar with Ramanujan's beautiful continued fraction, $$\cfrac{q^{1/5}}{1 + \cfrac{q} {1 + \cfrac{q^2} {1 + \cfrac{q^3} {1+\ddots}}}} = {\sqrt{5+\sqrt{5}\over ...
1
vote
2answers
158 views

Question regarding the Fibonacci sequence

Given the Fibonacci sequence $(F_1, F_2,F_3, ...)$ how do I prove that if $m|n$ then $F_m|F_n$? Can this be proven with mathematical induction?
0
votes
2answers
37 views

Proving a Recursive Formula

I know there are some questions on this site about how to find a recursive formula, but I've already found the formula. I'm doing an assignment (http://mathstat.dal.ca/~svenjah/math2112/Assign6.pdf) ...
13
votes
6answers
274 views

Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

How would I prove $$ \sum\limits_{\vphantom{\large A}i\,,\,j\ \geq\ 0}{n-i \choose j} {n-j \choose i} =F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of ...
0
votes
0answers
21 views

Prove equality of Fibonacci sequence

Let $u(n)$ — the Fibonacci sequence. Prove that $$u(1)^3+...+u(n)^3=\frac{ 1 }{ 10 } \left[ u(3n+2)+(-1)^{n+1}6u(n-1)+5 \right].$$ I suppose we need prove that equality by iduction in $n$. ...
2
votes
2answers
4k views

How to find the closed form to the fibonacci numbers? [duplicate]

Possible Duplicate: Prove this formula for the Fibonacci Sequence How to find the closed form to the fibonacci numbers? I have seen is possible calculate the fibonacci numbers without ...
0
votes
2answers
26 views

proof by induction for golden ratio and fibonacci sequence

I have to prove the following equation by induction for $$x = \phi$$ I am stuck and I don't know how to proceed. This is the equation $$ \phi ^n = f_n\phi + f_{n-1} $$ where $f_n$ is the nth term ...
19
votes
4answers
8k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
3
votes
3answers
108 views

Identity on Fibonacci numbers: $F_{2n}^2=F_{2n+2}F_{2n-2}+1$?

Let $F_n$ be the Fibonacci Sequence ($F_1=F_2=1, F_{n+2}=F_{n+1}+F_{n}$). Prove that $F_{2n}^2=F_{2n+2}F_{2n-2}+1$. I've tried everything from induction to telescoping series but I haven't got close. ...
0
votes
0answers
57 views

A binary plot of the Catalan numbers and the pseudo-Fibonacci series that can be found inside. Why do they appear?

I was trying to find in Internet a binary plot of the Catalan numbers, and I did not find anyone... so I did it by myself and here it is (about 2000 elements): There are not clear patterns inside ...
1
vote
2answers
32 views

Find $r$, given that $F_r= 2F_{101}+F_{100}$

Find $r$, given that $F_r= 2F_{101}+F_{100}$. We know that the recurrence relation for the Fibonacci sequence is $F_n= F_{n-1}+F_{n-2}$ and that $F_0 = F_1 = 1$, but how to proceed further?
4
votes
0answers
46 views

Finding first n so nth fibonacci is c modulo p

This is a question I stumbled upon in an online programming contest archive. The problem statement is simple, given $c \equiv F(n)$ mod $P$ and $P$, where $P$ is a prime of form 5$k$ + 1 or 5$k$ - 1, ...
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 ...
0
votes
1answer
81 views

Proving formulas with products of Fibonacci numbers

While digging through my old notes, I stumbled upon some formulas involving multiplication of Fibonacci numbers that I discovered about 7 years ago (being fascinated with Fibonacci numbers at the ...
1
vote
2answers
33 views

Fibonacci numbers relation

I was wondering if there was a relation between a Fibonacci number and its position. Is there a function $f(n)$ such that $$f(n)=F_n$$ where $F_n$ is the nth Fibonacci number?
18
votes
16answers
14k views

Applications of the Fibonacci sequence

The Fibonacci sequence is very well known, and is often explained with a story about how many rabbits there are after $n$ generations if they each produce a new pair every generation. Is there any ...
0
votes
1answer
40 views

How to find a formula relating fibonacci sequence?

By shifting property of fibonacci numbers, $$F_{m+n} = F_m · F_{n+1} + F_{m-1} · F_n$$ where $F_k$ denotes the kth Fibonacci number . I want to extend it to some n numbers . So , how to find a ...
1
vote
2answers
41 views

Generating Functions with Fibonacci

a) Let \begin{align*} F_{\text{even}}(x) &= F_0x^0 + F_2x^2 + F_4x^4 + F_6x^6 + F_8x^8 + \cdots \\ &= x^2 + 3x^4 + 8x^6 + 21x^8 + \cdots \end{align*} be the generating function whose ...
3
votes
1answer
75 views

Multiple of $p$ in first $p+1$ Fibonacci Numbers

Defining $F_0 = F_1 = 1$ and $F_{n+1} = F_{n} + F_{n-1}$ for $n>0$ gives the Fibonacci sequence, and it is well-known that modulo $p$, one of the first $p+1$ terms is $0.$ In fact, more is known, ...
3
votes
1answer
61 views

Dominos ($2 \times 1$ on $2 \times n$ and on $3 \times 2n$)

How many ways are there to tile dominos (with size $2 × 1$) on a grid of $2 × n$? How about on a grid of $3 × 2n$?
2
votes
0answers
139 views

What is wrong with my reasoning? (Irrational numbers / Fibonacci sequence) [closed]

I just noticed that: We define a procedure $\mathcal{I}:\mathbb{R}\rightarrow \mathbb{R}$ that output a real number. The probability to obtain an irrational or rational number via $\mathcal{I}$ is ...
4
votes
1answer
76 views

What's the Lucas version of the Möbius test for Fibonacci numbers?

I recently came across the following, attributed to Möbius: $$(a\in\mathbb N)=F_n\iff\left[\varphi a-\tfrac{1}{a},\varphi a+\tfrac{1}{a}\right]\ni(b\in\mathbb N)$$ It is the lesser-known test used to ...
2
votes
2answers
67 views

Fibonnaci and Lucas series technique

Well I have the following two problems involving fibonnaci sequences and lucas numbers, I know that they share the same technique, but I don't have clear the procedure: $$f_n = f_{n-1} + f_{n-2}: f_0 ...
1
vote
1answer
54 views

Proof Help dealing Lucas and Fibonacci Numbers

Claim: $L_n=F_{n-1}+F_{n+1}$ for all $n >0$ Could someone please help me prove this? My professor mentioned it in class, but didn't show us how to prove it. I am just curious. The $L$ stands for ...
0
votes
1answer
146 views

Solving a question about Fibonacci and Lucas numbers using induction

Im working on practice problems that the instructor gave us yesterday, and I absolutely have no clue of how to solve this problem.. I need to use mathmatical induction to solve this problem.. The ...
13
votes
4answers
297 views

How to prove $ \sum_{k=0}^n \frac{(-1)^{n+k}{n+k\choose n-k}}{2k+1}=\frac{-2\cos\left(\frac{2(n-1)\pi}{3}\right)}{2n+1}$

How to prove $$\sum_{k=0}^n \binom{n+k}{n-k}\frac{(-1)^{n+k}}{2k+1}=-\frac{2}{2n+1}\,\cos\left(\frac{2(n-1)\pi}{3}\right)\;\text{?}$$ I have a proof by induction for it, but it isn't simple! I want ...
1
vote
2answers
47 views

Why does Cassini's identity imply consecutive Fibonacci's number are relatively prime?

From Knuth's The Art of Computer Programming, Volume 1 on page 81 he gives Cassini's identity $F_{n+1} F_{n-1} - F_n^2 = (-1)^n$. Relation(4) and follows by saying "Relation(4) shows that $F_n$ ...
6
votes
1answer
85 views

Even Fibonacci Numbers and $\sqrt{5}$

My question is simple, but a mystery to me. Skip to the last paragraph if you're not interested in the story of my exploration. EDIT: I seem to have misinterpreted a key detail regarding how the ...
2
votes
1answer
47 views

What is the Lucas counterpart to the Fibonacci identity $5F_n^2\pm~4=\lambda^2$?

It's a well-known rule that a number $x$ belongs to the Fibonnaci Sequence iff: $$\begin{align}5x^2\pm~4&=\lambda^2&\lambda\in\mathbb Z\end{align}$$ In other words, if and only if $5x^2\pm~4$ ...
7
votes
1answer
293 views

Common terms in general Fibonacci sequences

Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For ...
2
votes
1answer
393 views

Lucas Numbers and Tilings

Show that $f_{n-1} + L_n = 2f_{n}$. So we need to find a $2$ to $1$ correspondence. Set 1: Tilings an $n$-board. Set 2: Tiling of an $n-1$-board or tiling of an $n$-bracelet. So we need to ...
14
votes
6answers
249 views

show that $\frac{1}{F_{1}}+\frac{2}{F_{2}}+\cdots+\frac{n}{F_{n}}<13$

Let $F_{n}$ is Fibonacci number,ie.($F_{n}=F_{n-1}+F_{n-2},F_{1}=F_{2}=1$) show that $$\dfrac{1}{F_{1}}+\dfrac{2}{F_{2}}+\cdots+\dfrac{n}{F_{n}}<13$$ if we use Closed-form expression ...
1
vote
1answer
43 views

Converting Fibonacci number $F_{5n+3}$ to Lucas numbers $L_{n+k}$

I'm trying to prove that$F_{5n+3}\text{mod}10 = L_{n}\text{mod}10$. I rearranged it into a more solvable form of $F_{5n+3}-L_n = 10k$ (because if two numbers end in the same digit, their difference ...
0
votes
0answers
49 views

Induction: Fibonacci / Lucas Numbers [duplicate]

From Andrews' Number Theory, Chapter 1, Section 1, Problem 15: Prove, by induction, that $F_{2n} = F_nL_n$ where $F_n$ denotes the nth Fibonacci number and $L_n$ denotes the nth Lucas ...
2
votes
1answer
215 views

An identity involving Lucas numbers

Let $L_n$ be the Lucas numbers, defined by $L_n = F_{n-1} + F_{n+1}$ where f is the Fibonacci numbers. How to prove that $L_{2n+1} = \displaystyle \sum_{k=0}^{\lfloor n + 1/2\rfloor}\frac{2n+1}{2n+1 ...
3
votes
2answers
232 views

Fibonacci/Lucas Number Congruences

Is there a compendium of well-known (and elementary) Fibonacci/Lucas Number congruences? I've proven the following and would like to know if it is (a) trivial, (b) well-known, or (c) possibly new. $$ ...
1
vote
1answer
34 views

Lucas Numbers Inequality

Can it be shown that \begin{align} \frac{1}{\ln(1+L_{n}) -1} \geq \frac{L_{n}}{(L_{n}-1)(e^{L_{n}}-1)} \end{align} where $L_{n}$ is the $n^{th}$ Lucas number. Show results in full detail.
0
votes
2answers
34 views

Express recursive function in Fibonacci

Given the Fibonacci function and the function $L_n = L_{n-1} + L_{n-2} + 1$, how do I go from this: $L_n + 1 = L_{n-1} + L_{n-1} + 1 + 1 \\ (L_n + 1) = (L_{n-1} + 1) + (L_{n-2} + 1)$ To this: $L_n = ...
44
votes
4answers
4k views

Eyebrow-raising pattern of number of primes between terms of the Fibonacci number sequence?

So, $$1,1,2,3,5,8,13,21...$$ Any connection to primes?...it appears not. However, in between the Fibonacci numbers are how much primes? Let's see: 1 and 1 ZERO 1 and 2 NADA 2 and 3 ZILCH 3 and 5 ZIP ...
2
votes
1answer
26 views

Is this Bertrand's postulate-related statement valid?

Bertrand's postulate says: For every $n>1$ there is always at least one prime $p$ such that $n<p<2n$. Is the following statement: For every $n>3$ there is always at least one ...
1
vote
2answers
71 views

How to solve the difference equation $u_n = u_{n-1} + u_{n-2}+1$

Given that: $$ \begin{equation} u_n=\begin{cases} 1, & \text{if $0\leq n\leq1$}\\ u_{n-1} + u_{n-2}+1, & \text{if $n>1$} \end{cases} \end{equation} $$ How do you solve this ...
4
votes
1answer
38 views

How to determine the generating function?

So I have $$\overset{*}{F} = \overset{*}{F}_{n-1} + \overset{*}{F}_{n-2} + g(n)$$ where $\overset{*}{F}$ is NOT a Fibonacci number for $n \geq 2$. $g(n)$ is any function $g: \mathbb{N} \to ...
4
votes
0answers
97 views

Fibonacci Quadratic Residue

After some research I have came up with a conjecture on Fibonacci quadratic residue: $F(x)^2 mod F(y)$ = { if y is even: $(F(|x-y|)^2$ } { if y is odd: $-(F(|x-y|)^2$ } for ...
2
votes
0answers
38 views

Fibonacci-related infinite sum

Prove that $$\sum_{n=0}^\infty \frac{1}{F_{2n+1}}=\frac{\sqrt{5}}{4}\theta_2^2\bigg(\frac{3-\sqrt{5}}{2}\bigg)$$ and $$\sum_{n=0}^\infty \frac{1}{F_{2n+1}+F_{2k-1}}=\frac{(2k-1)\sqrt{5}}{2F_{2k-1}}$$ ...
4
votes
1answer
42 views

How many Fibonacci Numbers are in the sequence

I have $I_n = \{2^n + 1, 2^n + 2, 2^n + 3, \dots , 2^{n+1}\}$ and I am trying to prove using induction how many Fibonacci numbers are there. First, the length of $I_n$ is $|I_n| = 2^n$ then for $F_0 ...
37
votes
5answers
789 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
0
votes
1answer
23 views

Proving $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ for $n \in \mathbb{N}_{>1}$ when $F_n$ is the nth Fibonacci number

Let $F_n$ be defined as the nth Fibonacci number. Prove that $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ with $n \in \mathbb{N}_{>1}$ My approach thus far was to use induction over $n$. ...
0
votes
3answers
43 views

Prove $F(n) < 2^n$ [closed]

Consider the Fibonacci function $\large{F(n)}$, which is defined such that $F(1) = 1, F(2) = 1$, and $F(n) = F(n−2)+F(n−1)$ for $n > 2$ I know that I should do it using mathematical induction but ...