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
1answer
606 views

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

This is a difficult problem from competition training: Is there among first 100000001 Fibonacci numbers one that ends with 0000? Trainer says use pigeonhole principle. I do not know how.
2
votes
1answer
40 views

Proving a Problem involving Fibonacci numbers

I'm working on proving the problem that states $\text {The sequence}$ {$F_n$} $\text {is defined by the} \ F_1=F_2=1, F_{n+2}=F_{n+1}+F_n \ \text {for} \ n \ge 1.$ $\text {For any natural number m, ...
1
vote
1answer
66 views

I don't know how to solve equations used in the golden ratio

Today i was reading something from golden ratio and i don't understand how some equations where solved for example: Im told that $\phi_{n+1}=B_{n+1} + \frac {A_n}{B_n}$. What I don't understand is ...
1
vote
2answers
61 views

Remarkable relation between Fibonacci numbers and its squares!

There is a remarkable relation between Fibonacci numbers and its squares: $F^{2}_{n} +F^{2}_{n+1}=F_{2n+1}$. I know how to prove it using $F_{n}=\frac{\sqrt{5}}{5}((\frac{1+\sqrt{5}}{2})^n ...
0
votes
0answers
67 views

Fibonacci sequence: Prove the formula $f_{2n+1}=f_{n+1}^2 + f_n^2$ [duplicate]

I can't seem to figure out this proof. I'm using weak induction and always get stuck during the inductive step. Prove for n > 0: $$f_{2n+1} = f_{n+1}^2 + f_n^2$$
0
votes
0answers
34 views

Count fractions between fibonacci

First a little run down on what I am doing: I have a large set of line graph data that I have collected. I've been looking at the graphs first at tick level then for the second chart I combine two ...
3
votes
3answers
51 views

When do you need to prove more than 1 base case in the Fibonacci problem?

I was trying to prove that if $F_n = F_{n-1} + F_{n-2}$ and $F_1 = 1$ and $F_2 = 1$, then the following proposition $P(n)$ was true $\forall n : \sum^n_{i=1}F_i=F_{n+2} - 1$ The issue I have with the ...
0
votes
0answers
120 views

Prime number distribution theory for dummies

For the distribution of prime numbers there is a hypothesis which predicts the possible positions of prime numbers called Riemann hypothesis ...
1
vote
0answers
25 views

How many rationals for a given $n \in \Bbb N \;\backslash \{1\}$?

Fix $n \in \Bbb N, n> 1$. Now choose a two digit base-$n$ number $ab $ say. There's $n^2$ choices for this. Consider the number $0.c_1 c_2 c_3 \ldots$ where the $c_i$ are defined recursively: ...
1
vote
1answer
39 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
1
vote
1answer
181 views

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if 1 and n also count as consecutive? It looks that the number of such subsets obeys the ...
4
votes
1answer
119 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 ...
8
votes
1answer
86 views

If the generating function summation and zeta regularized sum of a divergent exist, do they always coincide?

One could assign a value to divergent series by means of several summation methods. One summation method we could consider is the generating function method. Let's sum, for example, the fibonacci ...
0
votes
2answers
46 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 ...
5
votes
3answers
65 views

Fibonacci sequence: Given $n$ and $\mathrm{Fib}(n)$, is it possible to calculate $\mathrm{Fib}(n-1)$?

Given $n$ and $\newcommand{\Fib}{\mathrm{Fib}} \Fib(n)$, is it possible to calculate the previous number in the Fibonacci sequence - $\Fib(n-1)$ using integer math in constant time? In other words, I ...
1
vote
1answer
31 views

How do I proceed from here on finding the Binet's formula via generating functions?

So, I'm stuck with the algebra for the nth number on the Fibonacci sequence in here. I managed to get to the part where $G(x) = \frac{x}{1-x-x^2}$ $=$ $\frac{x}{(1-\alpha x)(1-\beta x)}$, and I know ...
-1
votes
1answer
56 views

using induction to prove that the formula for finding the n-th term of the Fibonacci sequence is: [duplicate]

May someone help me? I am trying to use induction to prove that the formula for finding the $n^{th}$ term of the Fibonacci sequence is: ...
3
votes
3answers
85 views

Proof by induction: $n$th Fibonacci number is at most $ 2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
1
vote
2answers
76 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
2
votes
1answer
98 views

Generalised Fibonacci

How to find the nth term of the recurrence in $\log n$ time. $$ \begin{array}{rcl} F[n]&=&F[n-1]+F[n-3]\\ F[2]&=&1\\ F[3]&=&2\\ F[4]&=&3\\ F[5]&=&4 \end{array} ...
1
vote
0answers
68 views

Sum of a Sequnce

How to find this sum $$ \sum_{i+j+k=n} \ G_i \cdot G_j \cdot G_k \ for \ all \ i,j,k > 0, $$ $$ G_i = i \cdot F_i, $$ where Fi - ith number Fibonacci, F0=0, F1=1
0
votes
3answers
72 views

Adding Fibonacci Numbers

I am getting confused on adding Fibonachi numbers. For example I know that: $\mathrm{F}_\mathrm{K+1}+\mathrm{F}_\mathrm{K}=\mathrm{F}_\mathrm{K+2}$ But I believe my logic is flawed. The way i am ...
1
vote
1answer
78 views

General formula of Fibonacci look alike series

I'm trying to discover the general formula of a series defined with recursion: $$ a_1 = 2, a_2 = 3, a_3 = 4 $$ and $$ a_n = a_{n-1} + a_{n-3} $$ It looks like Fibonacci, but the starting points are ...
0
votes
1answer
34 views

Initial values appear from nothing

This answer says that any casual sequence of the kind $y_n = y_{n-1} + y_{n-2} + y_{n-3} + \ldots $ will stay constant-0 because $y_0$ is a sum of zeroes, so is $y_1$ and the rest of the sequence. I ...
3
votes
2answers
90 views

Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
0
votes
1answer
57 views

Fibonacci Numbers in Nature

Supposedly the Fibonacci sequence appears naturally in nature, and my question is how, where and I guess why? I read that one way this is so is that it models the population of honey bees under ideal ...
0
votes
1answer
46 views

Generalized Fibonacci Sequence

I'm having trouble with a problem I encountered while studying Number Theory. This problem comes from the book Number Theory by George E. Andrews. It defines a generalized Fibonacci sequence $F_1$, ...
4
votes
2answers
44 views

Proving Fibonacci inequality

I didn't see a question regarding this particular inequality, but I think that I have shown by induction that, for $n>1$. I am hoping someone can verify this proof. ...
2
votes
2answers
122 views

Fibonacci number ending with given sequence of digits

Related to this question: For any given sequence of digits, does a Fibonacci number exist ending with such sequence? If not, it would be nice to find the smallest counterexample. (in other ...
8
votes
1answer
134 views

An analogue of Hensel's lifting for Fibonacci numbers

In this question Oleg567 conjectured the following interesting fact about Fibonacci numbers: $$ k\mid F_n\quad\Longrightarrow\quad k^d\mid F_{k^{d-1}n} $$ that can be regarder as an analogue of the ...
46
votes
4answers
3k views

Fibonacci number that ends with 2014 zeros?

This problem is giving me the hardest time: Prove or disprove that there is a Fibonacci number that ends with 2014 zeros. I tried mathematical induction (for stronger statement that claims that ...
0
votes
2answers
127 views

Fibonacci series, which is most pure mathematically? [closed]

There are various methods of generating the Fibonacci series. I'm going to list 3 of them in this question. Method 1: f[n] = f[n - 1] + f[n - 2] Method 2: (more ...
1
vote
1answer
35 views

Order of convergence for the method of false position

I'm reading about the order of convergence of the method of false position and there is one tricky point in the proof I don't understand. The method itself for finding the minimum $x^*$ of a function ...
2
votes
0answers
78 views

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

I am looking at the following exercise: $$\text{ Show with induction,that the } i^{th} \text{ number Fibonacci satisfies the equality: } $$ $$F_i=\frac{\phi^i-\hat{\phi}^i}{\sqrt{5}}$$ where $\phi$ ...
3
votes
1answer
56 views

Find a sequence

Find the function for the sequence $a_0 = 0, a_1 = 1$ and $a_{n}=a_{n+10}+a_n$ for all $n>0$.
1
vote
3answers
85 views

How to compute the nth number of a general Fibonacci sequence with matrix multiplication?

If we want to compute the nth Fibonacci number we just power the matrix $M = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]$ $n$ times and we get $M =\left[ \begin{array}{cc} ...
2
votes
1answer
76 views

The number of partitions of $n$ and the $n$th Fibonacci number.

I'm very sorry if this is a duplicate in any way. There's a lot of material out there on connections between these sequences so it's a possibility . . . Let $P_n$ be the number of partitions of $n$ ...
-1
votes
1answer
62 views

Checking a formula works for many numbers [closed]

Hello StackExchange users. I have discovered a formula which works out any Fibonacci number using the formula to work out the value of any cell in Pascal's triangle. It uses the sigma notation which I ...
3
votes
1answer
120 views

Golden ratio, $n$-bonacci numbers, and radicals of the form $\sqrt[n]{\frac{1}{n-1}+\sqrt[n]{\frac{1}{n-1}+\sqrt[n]{\frac{1}{n-1}+\cdots}}}$

The following infinite nested radical $$\sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}}$$ is known to converge to $\phi=\displaystyle\frac{\sqrt{5}+1}{2}$. It is also known that the similar infinite ...
13
votes
4answers
365 views

Converting recursive equations into matrices

How do we convert recursive equations into matrix forms? For instance, consider this recursive equation(Fibonacci Series): $$F_n = F_{n-1} + F_{n-2}$$ And it comes out to be that the following that ...
1
vote
1answer
69 views

Fibonacci numbers $F_{n+3} + F_{n} = 2F_{n+2}$

Prove $F_{n+3} + F_{n} = 2F_{n+2}$ for any positive integer n. So What I did was this: fn+ fn+1 = fn+2 fn + fn+1 = fn+2 => fn+2 -fn+1 fn+1 + fn+2 = fn+3 then I subsituted into equation in ...
1
vote
4answers
133 views

Fibonacci Calculation using a larger matrix

So the formula to generate the fibonacci sequence in matrix form is: $$ \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & ...
11
votes
5answers
1k views

How to tell if a Fibonacci number has an even or odd index

Given only $F_n$, that is the $n$th term of the Fibonacci sequence, how can you tell if $n \equiv 1 \mod 2$ or $n \equiv 0 \mod 2$? I know you can use the Pisano period, however if $n \equiv 1$ or ...
0
votes
1answer
46 views

Base case in the Binet formula (Proof by strong induction)

I don't understand why the author says that the inductive formula does not apply until $u_3$. The formula does not depend on other terms in the Fibonacci sequence, so I thought I could just prove it ...
1
vote
2answers
70 views

How to establish this inequality without using induction?

Given the Fibonacci sequence $a_1 = 1$, $a_2 = 2$, $\ldots$, $a_{n+1} = a_n + a_{n-1} $ for $n \geq 2$, how to derive, without using induction, the inequality $$ a_n < (\frac{1+\sqrt{5}}{2})^n $$ ...
-1
votes
1answer
156 views

Asymptotic value of Fibonacci numbers

It is well known that $F_n\sim\frac{\phi^n}{\sqrt{5}}$, where $\phi=\frac{1+\sqrt{5}}{2}$. Does someone know a better estimate? With proof please. I'm trying to calculate the following limit: Let ...
0
votes
1answer
72 views

Let $u_n$ be the $n$-th entry in the Fibonacci sequence $1,1,2,3,5,8,13,\ldots$

If you start with $u_1 = 1$ and $u_2 = 1$, then the sequence can be generated using the formula $$u_{n+1} = u_n + u_{n-1}\ .$$ If $u_n = r^n$, what is r? Can anyone figure this out? I am so stuck ...
4
votes
2answers
119 views

The sum of $n$ consecutive Fibonacci numbers.

The sum of $8$ consecutive Fibonacci numbers is divisible by $3$. How can I generalize this for the sum of $n$ consecutive Fibonacci numbers? For example, $$1+1+2+3+5+8+13+21=54=3\times 18 \\ ...
1
vote
1answer
61 views

Proof that golden angle successively divides the largest gap by the golden ratio?

The golden angle divides the circumference of a circle by the golden ratio. "If radial spokes are placed successively into the circle, each spaced by a golden angle increment, then each additional ...
2
votes
1answer
54 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 ...