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
25 views

Prove that $\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$ [duplicate]

I am asked: Let $F_{i}$ denote the $i$-th Fibonacci number. Prove that $$\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$$ I have the base case and the inductive hypothesis, but I'm not sure what ...
4
votes
2answers
8k views

Roulette betting system probability

The Fibonacci is a popular Roulette betting system that is based on a naturally occurring mathematical sequence. The sequence itself is cumulative. In other words, the next number is equal to the sum ...
27
votes
2answers
837 views

Fibonacci $\equiv -1 \mod p^2$

Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify. EDIT: In response to ...
7
votes
2answers
354 views

Prove Divisibility In Fibonacci Sequence Over A Prime Number

In The Fibonacci sequence which is defined as $$ F_n=F_{n-1}+F_{n-2}, $$ lets say we have the number $p$ which is an odd prime. Prove that: $F_{p-1} + F_{p+1} -1$ Is divisible by $p$. Prove that ...
1
vote
0answers
53 views

Help me find the mistake in my solution of the limit

Let $x_1=1, x_2=2,$ $$x_n=x_{n-1}+x_{n-2}, (n>2)$$ The task is to find: $$\lim \limits_{x\to\infty}\frac{x_{n+1}}{x_n}!$$ My attempt at solution: We write the recursive formula as: ...
4
votes
1answer
25 views

First Fibonacci Number with Given Remainder

I wonder is there more effective algorithm than brute-force-search to find the first Fibonacci number with given remainder $~~r~~$ modulo given integer $~~m~~$. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
5
votes
0answers
62 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 ...
0
votes
2answers
193 views

Rate of Convergence vs Radius of Convergence

What is the difference between finding the 'rate of convergence' and the radius of convergence'? The question I am trying to solve here is to find the rate of convergence of the ratio of Fibonacci ...
5
votes
3answers
277 views

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$

Prove: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; I was stuck with this question for a while... Help me please!!! Thanks!!!
2
votes
1answer
68 views

On $4n+1 = x^2, 5n+1 = y^2$ and the Fibonacci numbers

While answering this question, I decided to look at the particular case, $$4n+1 = x^2\\5n+1 = y^2$$ to be solved simultaneously. The solutions for $n,x,y$ are A157459, A007805, and A049629, ...
9
votes
1answer
362 views

Infinite sum of reciprocal shifted Fibonacci numbers

I found on Wikipedia the following infinite sum : $$\sum_{k=0}^{\infty} \frac{1}{1+F_{2k+1}}=\frac{\sqrt{5}}{2}$$ There is no reference for this sum in the article and I couldn't find it ...
12
votes
0answers
121 views

Do all rational numbers repeat in Fibonacci coding?

In a regular, positional number system (like our decimal numbers), every rational number ends in a repeating sequence (even if it's just 0). For example, 1/3 in base 10 is 0.33333..., in base 5 it's ...
1
vote
0answers
44 views

Does 1/4 eventually repeat in Fibonacci coding?

In a regular, positional number system (like our decimal numbers), every rational number ends in a repeating sequence (even if it's just 0). For example, 1/3 in base 10 is 0.33333..., in base 5 it's ...
6
votes
1answer
218 views

Prove $F_{1}^{2}+F_{2}^{2}+\dots+F_{n}^{2}=F_{n}F_{n+1}$ using geometric approach

Prove the identity: $F_{1}^{2}+F_{2}^{2}+\dots+F_{n}^{2}=F_{n}F_{n+1}$, where $F_i$ denotes a Fibonacci number. How can I prove it using a geometric approach?
0
votes
1answer
47 views

Need help calculating probability…

First time here, so I hope you'll not get too frustrated if I make any etiquette mistakes for this forum. So here's my question. I know there are snow day calculators out there, but I'm trying to ...
5
votes
4answers
2k views

For the Fibonacci numbers, show for all $n$: $F_1^2+F_2^2+\dots+F_n^2=F_nF_{n+1}$

The definition of a Fibonacci number is as follows: $$F_0=0\\F_1=1\\F_n=F_{n-1}+F_{n-2}\text{ for } n\geq 2$$ Prove the given property of the Fibonacci numbers for all n greater than or equal to 1. ...
1
vote
0answers
25 views

Find length of sequence with fibonacci principle

Let assume we have sequence: $${l_{n + 1}} = {l_n} + {l_{n - 1}} $$ $$\begin{array}{l}{l_0} = 0\\{l_1} = 01\\{l_2} = 010\end{array}$$ Our goal to get $|{l_n}|$ (length). For ${l_0}$ it's 0, for ...
1
vote
2answers
42 views

Proof and geometrical significance of $F(n+1)^2-F(n) \cdot F(n+2)$?

My son notes that for Fibonacci numbers $F_n$, $$ (F_{n+1})^2-F_n \cdot F_{n+2} =(-1)^n $$ I assume that this is true. Update: I see that the proof is already here: Prove the given property of the ...
9
votes
1answer
3k views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
0
votes
0answers
41 views

Is the following statement true: $F_n\leq p\leq F_{n+2}$

Let be $n\in\{2,3,\ldots\}$ Is the following statement true: There exists a prime number so that $F_n\leq p\leq F_{n+2}$ while $F_n$ is a Fibonacci number.
6
votes
1answer
607 views

Flaw in induction proof that the Fibonacci sequence is bounded by $(5/3)^n$

The Fibonacci sequence is defined by $a_1 = 1, a_2 = 1$ and for all $n \ge 2, a_{n+1} = a_n + a_{n-1}$. Thus the sequence begins $$1,1,2,3,5,8,13,21,...$$ Prove that for all $n \ge 1, a_n ...
0
votes
2answers
300 views

Proof of the inequality $F_i<(5/3)^i$ for the Fibonacci numbers

The example states: As an example, we prove that the Fibonacci numbers, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5,..., Fi = Fi - 1 + Fi - 2, satisfy Fi < (5/3)i, for all i >= 1. To do this, we ...
4
votes
1answer
62 views

Fibonacci sequence digits

We define the Fibonacci sequence by $F_{n+2}=F_{n+1}+F_{n}$, with $F_0=0$ and $F_1=1$. How to compute the last $30$ digits of $F_{2^{200}}$ for instance? can we use Python?how?
2
votes
0answers
77 views

Fibonacci Numbers and the Harmonic Series

$$\sum_{k=1}^{n} \frac{1}{k}=H_n=\frac{p_n}{q_n}$$ Where $p_n,q_n$ are coprime intergers. The first few values for $p_n+q_n$ are $2,5,7,37,197,69,504,1041,9649$. When are $p_n+q_n$ Fibonacci ...
4
votes
1answer
104 views

Some heuristics about the Pisano Period, primes and Fibonacci primes. What reasons are behind them?

I started to read about the Pisano Period, $\pi(n)$, applied to the classic Fibonacci sequence and made some simple tests looking for possible properties of the sequence. I have observed the following ...
1
vote
2answers
89 views

Domino tiling extended in N dimensions.

The standard domino tiling problem, is the number of ways to tile a board of size 2xn by dominos of size 2x1. The answer directly follows a recursion, the same as the Fibonacci series. If I extend ...
0
votes
1answer
31 views

Is there some function which return probability to select prime number from $n$ first Fibonacci numbers.

So my question is: is there function return probability to select prime number from $n$ first Fibonacci numbers. So maybe it realize with $\pi(n)$ function?
1
vote
1answer
36 views

How is this identity for Fibonacci numbers called?

In the course of proving another identity, I've found that $$F_n \equiv F_kF_{n-k+1} + F_{k-1}F_{n-k}$$ …for all corresponding n and ...
9
votes
2answers
144 views

Show that for a given $s$ there are a finite number of Fibonacci number of form $n^2+s$

It is well known that the last Fibonacci number $F_k$ such that $\exists \ n \in \Bbb{N} : F_k = n^2$ is $144$. Thus there are only $4$ perfect squares among the Fibonacci sequence (assuming you ...
0
votes
2answers
162 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
4answers
105 views

Fibonacci inequality

If $F_n$ denotes the $n$-th Fibonacci number ($F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n$), show that the inequalities $F_{2n-2} < F_n^2 < F_{2n-1}$ hold for all $n ≥ 3$.
3
votes
1answer
1k views

Exponential lower bound for Fibonacci numbers

Can someone show me how to solve through induction, $F(N) \geq (3/2)^N$ for all $N\geq N_0$, where $F(n)$ is the Fibonacci function and $N_0$ is some positive integer. I know that $N_0$ should be ...
2
votes
1answer
40 views

Is it rational or not?

I have two interesting question : Is this number rational or not: $$0.F_{1}F_{2}F_{3}...$$, where $F_{i}$ - Fibonacci number. And is this number rational or not: $$0.p_{1}p_{2}...$$
58
votes
3answers
691 views

Closed form solution for $\sum_{n=1}^\infty\frac{1}{1+\frac{n^2}{1+\frac{1}{\stackrel{\ddots}{1+\frac{1}{1+n^2}}}}}$.

Let $$ \text{S}_k = \sum_{n=1}^\infty\cfrac{1}{1+\cfrac{n^2}{1+\cfrac{1}{\ddots1+\cfrac{1}{1+n^2}}}},\quad\text{$k$ rows in the continued fraction} $$ So for example, the terms of the sum $\text{S}_6$ ...
9
votes
2answers
273 views

A number $N$ is a $k$-nacci number if and only if …

For $k\ge 2\in\mathbb N$, one can define the $n$-th $k$-nacci number $f_k(n)\ (n=0,1,\cdots)$ as $$f_k(0)=f_k(1)=\cdots=f_{k}(k-2)=0,\ \ ...
1
vote
2answers
70 views

Seeking a combinatorial proof $F_{mn}$ always a multiple of $F_m$

I would appreciate if somebody could help me with the following problem Q: Let $F_n$ the sequence of Fibonacci numbers, given by $F_1 = 1, F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$ ...
5
votes
2answers
75 views

Find $\mathrm{lcm}(F_{m},F_{n},F_{k})$.

So consider three Fibonacci numbers. My question is: Find $\mathrm{lcm}(F_{m},F_{n},F_{k})$, where lcm is least common multiple.
0
votes
0answers
27 views

Is the “Fibonacci square tiling” of Fibonacci-sided rectangles always optimal?

Is an optimal square tiling of a rectangle with side lengths of successive Fibonacci numbers always the sequence of Fibonacci numbers, as in the picture below?
2
votes
0answers
111 views

Can I use the equality $\phi^2=\phi+1$ without proving it?

I am looking at the following exercise: Show with induction, that the $i^{\rm th}$ Fibonacci number satisfies the equality: $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
11
votes
5answers
8k views

Why does the Fibonacci Series start with 0, 1?

The Fibonacci Series is based on the principle that the succeeding number is the sum of the previous two numbers. Then how is it logical to start with a 0? Shouldn't it start with 1 directly?
6
votes
2answers
907 views

Is there among first $100000001$ Fibonacci numbers one that ends with $0000$?

This looks like a difficult problem: Is there among first $100000001$ Fibonacci numbers one that ends with $0000$? (it is from a competition training; trainer suggests using pigeonhole ...
1
vote
1answer
61 views

Convergence of Fibonacci quotients

Let $F_n=F_{n-1}+F_{n-2},~ F_0=0,~F_1=1~$ be the Fibonacci numbers. Then it is well known that $\lim_n \frac{F_{n+1}}{F_n}=\frac{1+\sqrt{5}}{2}$. However, many textbooks proved the above by using ...
2
votes
1answer
47 views

Fibonacci identity $F_{n+1}^2 - (F_{n+1}F_n) - F_n^2 = (-1)^n$

I am trying to prove Let $F_n$ be the $n$th Fibonacci number. Then $F_{n+1}^2 - F_{n+1}F_n - F_n^2 = (-1)^n$ I am not sure where to start with this.
0
votes
2answers
26 views

If $y_n = 2x_n-1$, show that $y_{n+1} = y_n + y_{n-1} + 1$

If $y_n = 2x_n-1$, how do you show $y_{n+1} = y_n + y_{n-1} + 1$ with $y_0 = 1$ and $y_1 = 1$? Would you start with $y_{n+1} = y_n + y_{n-1} + 1$, find a formula for $y_n$ and then compare it with ...
0
votes
1answer
49 views

How do you show $s_n = \frac{x_{n+1}}{x_n}$ where $(x_n)$ is the Fibonacci sequence?

Let $(s_n)$ denote the sequence satisfying: $s_{n+1} = 1 + \frac{1}{s_n}$ with $s_0 = 1$. Let $(x_n)$ denote the Fibonacci sequence and $x_n = \frac{5 + \sqrt{5}}{10}(\frac{1 + \sqrt{5}}{2})^n + ...
1
vote
1answer
65 views

Limit as $n \to \infty$ of $\frac{x_{n+1}}{x_n}$ in the Fibonacci sequence

Given that $x_n = \frac{\sqrt{5}+5}{10} (\frac{1 + \sqrt{5}}{2})^n + \frac{5 - \sqrt{5}}{10}(\frac{1 - \sqrt{5}}{2})^n$ How do you show that $\lim_{n \to \infty} \frac{x_{n+1}}{x_n}$ is the ...
0
votes
1answer
59 views

formula for the nth term of this sequence?

How do you find a formula for the nth term of this sequence? given that $x_n$$_+$$_1$ = $x_n$ + $x_n$$_-$$_1$ (Fibonacci sequence) and $x_0 = 1$ and $x_1 = 1$. Do i complete the square on $x^2 - x - ...
1
vote
2answers
39 views

Finding the limit of the following series, wherever it is convergent

Let $ f(x) = \sum_{n=1}^{\infty}a_nx^n $ where $a_n$ is the nth Fibonacci number. Find the values for which the series is convergent, and find $f(x)$ for those values. (i.e - find the limit when ...
5
votes
1answer
67 views

Limit of a specific sequence involving Fibonacci numbers.

Let, $\left\{F_n\right\}_{n=1}^\infty$ be the Fibonacci sequence, i.e, $F_1=1, F_2=1~\&~ F_{n+2}=F_{n+1}+F_n~\forall ~n \in \mathbb{Z}_+$ Let, $P_1=0, P_2=1$. Divide the line segment ...
1
vote
2answers
47 views

Proof concerning Fibonacci and recursively defined sequences

The series $(a_n)_{n\in\mathbb{N}}$ is given through $$a_1=1,\quad a_2=\frac{1}{2},\quad a_{n+2}=a_na_{n+1} \quad\text{ for } n\geq1.$$ I want to show that $$a_n = 2^{-f_{n-1}}$$ whereas ...