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

0
votes
1answer
22 views

New Identities for Generalized Fibonacci Numbers?

Over the past few months I have been investigating one the generalizations of the Fibonacci numbers, called the Generalized Fibonacci Numbers (GFNs). The GFNs are just like the regular Fibonacci ...
21
votes
7answers
949 views

How are we able to calculate specific numbers in the Fibonacci Sequence?

I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...
1
vote
1answer
40 views

Induction proof for Fibonacci numbers

I am trying to get a hang on the induction method for proof, but I'm still dubious of many aspect of this proof regarding its application to sequences of integers, such as the Fibonacci sequence. ...
1
vote
3answers
27 views

Proving this $F_{n+1} \cdot F_{n-1} - F^2_n = (-1)^n$ by induction

Where $n \in \mathbb{N}$ and $$ F_n = \begin{cases} 0 & \text{ if } n = 0 \\ 1 & \text{ if } n = 1 \\ F_{n-1} + F_{n-2} & \text{ if } n > 1 ...
2
votes
1answer
35 views

What does “The closure of the shift-orbit of the Fibonacci word” mean?

Im trying to translate an article about rauzy fractal. But since my English is not good enough I cant understand this paragraph: ...
1
vote
1answer
22 views

How can we be sure of periodicity by testing some terms?

A mod $n$ Fibbonaci sequence is simply defined as the Fibbonaci sequence, except all terms are in mod $n$. Now to determine periodicity, the worked solutions computed the first 20 or so terms and ...
3
votes
2answers
50 views

How is the Binet's formula for Fibonacci reversed in order to find the index for a given Fibonacci number?

a question about the Fibonacci sequence: $$F_n =\frac{\phi^n-(-\frac{1}{\phi})^n}{\sqrt{5}}$$ This is the Binet's formula for the nth Fibonacci number. if I reverse it I can get: ...
1
vote
2answers
39 views

Proof By Induction Fibonacci Numbers

How do I prove that $$ f_{ 2n+1 } = 3f_{ 2n } + 1 - f_{ 2n-3 } $$ I'm not sure how to prove it using the defining recurrence of Fibonacci numbers.
0
votes
3answers
63 views

How to prove the convergence of $\lambda_n = \frac{f_{n+1}}{f_n}$?

A question about the fibonacci sequence. I have a sequence: $$\lambda_n = \frac{f_{n+1}}{f_n}$$ While $f_n$ is the fibonacci sequence. I also have the equation: $$ 0 = x^2 - x -1$$ And i know ...
6
votes
0answers
53 views

Remainders of Fibonacci numbers

Let $a>b$ be positive integers. Is there a Fibonacci number that is $b$ modulo $a$? We know that the Fibonacci numbers are periodic modulo $a$. Indeed, consider pairs $(F_i,F_{i+1})$ modulo $a$. ...
0
votes
1answer
20 views

Why the number of subsets S ⊂ {1,…,n} without an odd number of consecutive integers is F(n+1)?

I have two questions about the Fibonacci sequence: I read from Wikipedia: 1) The number of subsets S ⊂ {1,...,n} without an odd number of consecutive integers is F(n+1). 2) The number of ...
0
votes
1answer
60 views

Reccurence Relation of Subsets

How many subsets does the set S = {1,2,...,n} have that contain no two consecutive integers? Assuming that the number of subsets is f(n), you need to find a recurrence relation and its initial ...
1
vote
2answers
26 views

Fibonacci divisibility

Prove that the following holds: $3|F_n$ if and only if $4|n$ Base case for $n=1$: $F_1$=1, so $F_1$ is not divisible by 3 and 1 is not divisble by 4. So the proposition holds for $k=1$ Continue ...
5
votes
0answers
67 views

Product of consecutive Fibonacci numbers divisibility

Prove that the product of any $k$ consecutive Fibonacci numbers is divisible by the product of the first $k$ Fibonacci numbers. We can try to show that for every prime $p$, the power of $p$ appearing ...
8
votes
2answers
416 views

Square Fibonacci numbers

Are there Fibonacci numbers other than $F_0 = 0 = 0^2, F_1 = F_2 = 1 = 1^2,$ and $F_{12} = 144 = 12^2$ which are square numbers? If not, what is the proof?
1
vote
3answers
46 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$.
1
vote
1answer
41 views

Recurrence Fibonacci Sequence Proof

I'm having troubles proving that in a fibonacci sequence if n is divisible by four, then Fn is divisible by three So when Fn is 6, n is 8 and so on. I was thinking maybe I could use mod 3 or mod 4 ...
11
votes
4answers
4k 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?
18
votes
2answers
1k views

Understanding this pattern behind the Fibonacci sequence

To be honest, I'm pretty awful at mathematics however, when up till 6AM I do like to do random things throughout the night to keep me occupied. Tonight, I began playing with the Fibonacci sequence in ...
4
votes
1answer
475 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
3answers
33 views

Uniform Convergence for a sequence of functions defined by recurrence

The following is a problem that I can't solve, and I need some tips: Problem: For $x>-1$, define $f_1(x) = x,\ f_{n+1}=\dfrac{1}{1+f_n(x)}$. Find the limit function $f(x)$ and all the subsets of ...
1
vote
0answers
40 views

Proving an equation dealing with Fibonacci numbers

Prove that: $f(2 \cdot k) = f(k) \cdot f(k) + f(k - 1) \cdot f(k - 1)$ Where $f(k)$ is the kth Fibonacci number. Also prove that: $f(2 \cdot  k + 1) = f(k) \cdot  f(k + 1) + f(k - 1)  \cdot f(k)$ ...
0
votes
2answers
39 views

How to show that the limit of a fibonacci sequence equates to 1 as n goes to infinity

$$\lim_{n \to \infty} \frac{f_{n+1} f_{n-1}}{f_n^2} = 1$$ I tried expanding both the numerator and denominator to probably cancel out but that did not work... I also split it up into different ...
0
votes
1answer
46 views

Prove $f_{n}^{2} = f_{n-2}f_{n+2}+(-1)^{n}$ $n\ge 3$

Prove $f_{n}^{2} = f_{n-2}f_{n+2}+(-1)^{n}, n\ge 3$ (For the sake of space, I'm going to skip the basis step and move straight to the inductive step.) Inductive Step: Assume P(n) is true, prove ...
0
votes
1answer
42 views

Proof of: $f_{n}^{2} = f_{n-1}f_{n+1}+(-1)^{n+1}$

So I'm going over some examples of recursion and Fibonacci Sequences for my quiz tomorrow and I'm a bit lost after a certain point. Prove $f_{n}^{2} = f_{n-1}f_{n+1}+(-1)^{n+1}$ $n\geq 2$ Basis ...
0
votes
0answers
35 views

Inductive proof of the property $f(k+2)=f(k)+f(k+1)$ for the numbers given in terms of the golden ratio [duplicate]

Help prove through induction that $f(k+2)=f(k)+f(k+1)$ using the golden ratio $\frac1{\sqrt5}\phi^n-\frac1{\sqrt5}\left(\frac{1-\sqrt5}2\right)^n$ $F_{n+2}=F_n+F_{n+1}$, using golden ration $f_n = ...
6
votes
1answer
57 views

Does this sequence contain all positive integers?

Set $a_1 = 1$. Then $a_n$ is chosen to be the smallest distinct positive integer such that $$\frac{\sum_{i = 1}^n a_i}{n}$$ is a Fibonacci number. If my calculations are correct, the sequence starts ...
9
votes
2answers
860 views

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

In a paper that I wrote as an undergraduate student, I conjectured that the only integer solutions to the equation $$|5x^2 - y^2| = 4$$ occur when $x$ is a Fibonacci number and $y$ is a Lucas number. ...
1
vote
0answers
55 views

Mean and Variance of Fibonacci Numbers

I would like to ask the community for feedback regarding the following two conjectures of mine: $\textbf{Conjecture 1}$ Let $\mathcal{F}_N^- = \{F_n:-N \leq n < 0\}$, i.e. be the set of Fibonacci ...
0
votes
0answers
26 views

What's the point of Fermat (and other) numbers?

The title says it all. I mean anybody can can make up a sequence like Fn = (F(n-1) - 1)^3 + 3 or something like that- why is Fermat (or Fibonacci or whatever) numbers better or more important?
0
votes
1answer
32 views

how to calculate a modified fibonacci via matrix exponentiation

If I modify the fibonacci recurrence to be the following way: f(0) = 1 f(1) = 1 f(N) = f(N - 1) + f(N - 2) + 1 Is it possible to represent this recurrence in a matrix equation similar to the one ...
4
votes
1answer
42 views
8
votes
1answer
332 views

Construction of generating function from identity

I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
0
votes
0answers
20 views

geometric proof for fibonacci numbers identity with sum of two squares

Induction Proof: Fibonacci Numbers Identity with Sum of Two Squares The link above gives the induction proof does a geometric proof using the squares with Fibonacci length exist for this?
1
vote
2answers
59 views

Use Fibonacci number to prove that is the integer that is closest to another number

Hi everyone, I don't really understand the problem. I have the following hint, but I don't know how to work it.
0
votes
0answers
32 views

Proof for $\gcd(F_m,F_n)=F_{\gcd(n,m)}$ [duplicate]

I saw many questions/answers, where: $$\gcd(F_m,F_n)=F_{\gcd(n,m)}$$ is taken as a fact. But how can I actually prove that this is true?
10
votes
3answers
584 views

Infinite Series: Fibonacci/ $2^n$

I presented the following problem to some of my students recently (from Senior Mathematical Challenge- edited by Gardiner) In the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... each term ...
2
votes
4answers
89 views

Find the sum of an infinite series of Fibonacci numbers divided by doubling numbers. [duplicate]

How would I find the sum of an infinite number of fractions, where there are Fibonacci numbers as the numerators (increasing by one term each time) and numbers (starting at one) which double each time ...
2
votes
2answers
61 views

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

Please help! I need help on my assignment for discrete mathematics! Prove the following identity: $\binom{n} {0} F_0+\binom{n}{1} F_1+\binom{n}{2} F_2+\cdots +\binom{n}{n} F_n=F_{2n}$ I need to ...
2
votes
0answers
19 views

Symmetric Fibonacci images

I was playing with the Turtle module in Python and decided to try plotting the Fibonacci series with the following scheme where $f_n$ is the $n^{th}$ Fibonacci number: Rotate the turtle $k (f_n ...
0
votes
0answers
33 views

Proof of a formula for generalized Fibonacci numbers

I have done the verification for $$U_rU_{n−1} − U_{r−1}U_n = (−1)^{r−1}U_{n−r}$$ I realized when I was doing for $n=k+1$, the expression $U_rU_k − U_{r−1}U_{k+1}$ would not equate to ...
0
votes
0answers
18 views

Calculating the hitting probability using the strong markov property

We have the following Markov chain. $X_n=(F_{n-1},F_n)$ where $F_0=0, F_1=1$ and with probability 1/2 $F_{n+1}$ is the difference of $F_{n-1}$ and $F_{n}$ and with probability 1/2 the sum. I have to ...
2
votes
1answer
42 views

How to find $\sum_{n = 0}^{ \infty} \frac{F_n}{3^n}$

How can I find $$\sum_{n = 0}^{ \infty} \frac{F_n}{3^n}$$ If I know that the generating function for the Fibonacci sequence is $G(t) = \frac{t}{1 - t - t^2}$?
1
vote
2answers
59 views

Proof a number is Fibonacci number

I have a question regarding the proof that a number n is a Fibonacci number if and only if $5n^2-4$ or $5n^2+4$ is a perfect square. I don't understand the second part of the proof: knowing that ...
8
votes
4answers
86 views

Proof of ${F(n+4)}^{4} - {4F(n+3)}^{4} - {19F(n+2)}^{4} - {4F(n+1)}^{4}+{F(n)}^{4} = -6$

Observe: \begin{matrix} F(n)|&{F(n)}^{4}& - {4F(n+1)}^{4}& - {19F(n+2)}^{4}&- {4F(n+3)}^{4}&{F(n+4)}^{4}& = -6\\ 1|& 1& -4& -304& -324& 625&=-6\\ ...
1
vote
0answers
38 views

Applying Fibonacci Fast Doubling Identities

So I sort of understand of how these identities came about from reading this article. $F_{2n+1} = F_{n}^2 + F_{n+1}^2$ $F_{2n} = 2F_{n+1}F{n}-F_{n}^2 $ But I don't understand how to apply them. ...
1
vote
0answers
44 views

proving Fibonacci numbers using mathematical Induction?

Can anyone confirm whether my answer is correct, please. Let suppose we have the following fibonacci numbers as shown: $f(0) = 0, f(1) = 1$, and $f(n) = f(n-1) + f(n-2)$ for $n \geq 2$. Prove that ...
2
votes
1answer
241 views

Cycles in the Generalized Fibonacci Sequence modulo a Prime

Suppose I have a fibonacci sequence 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 Now if I have a modulo 5 fibonacci sequence,it will look like ...
0
votes
1answer
55 views

Prove that for each Fibonacci number $f_{4n}$ is a multiple of $3$. [duplicate]

The Fibonacci numbers are defined as follows: $f_0 = 0$, $f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for $n \ge 2$. Prove that for each $n \ge 0$, $f_{4n}$ is a multiple of $3$. I've tried to prove to ...
1
vote
6answers
307 views

A Non-recursive Fibonacci Sequence

How can I determine the general term of a Fibonacci Sequence? Is it possible for any one to calculate F2013 and large numbers like this? Is there a general formula for the nth term of the Fibonacci ...