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

4
votes
3answers
215 views

Inequality of the Fibonacci sequence and the golden ratio

How can I prove that for each $n\in\Bbb Z^+$ $$\frac{f_{2n}}{f_{2n-1}}\leq\frac{1+\sqrt{5}}{2}$$ where each $f_i$ is a term of the Fibonacci sequence. Any help is really appreciated
1
vote
2answers
51 views

Find $x$ as the given $n$th term in the Fibonacci sequence?

With a given $n$ and I am trying to find the value of $x$, as in: $$Fib(x)=n$$ Using the formula for Fibonacci sequence, where $\varphi$ is the Golden Ration ($\approx1.61803399\ldots$) $$Fib(z) = ...
2
votes
3answers
74 views

Writing $1+3x^2+8x^4+21x^6+\cdots$ as a power series representation

How would I write the power series $$1+3x^2+8x^4+21x^6+\cdots$$ as a power series representation (something neat similar to $\frac{1}{1-x}$)? This reminds me of the power series ...
1
vote
4answers
60 views

How to prove this equation by induction?

I am trying to prove this equation by mathematical induction $$f_{n+1}f_{n-1} = f_{n}^{2}+(-1)^n$$ is true where $f_{n} = $ the nth number in the Fibonacci sequence. I don't quite get how to do this ...
0
votes
2answers
34 views

Problem on deriving binet formula

I'm trying to understand binet formula. I got a good explanation here. Please look at the link. Everything just fine but one thing. It said that $A_n = A_{n-1} + A_{n-2}$, which is fibonacci. But why ...
2
votes
3answers
83 views

Showing convergence of recursive sequence $A_{n+1}=\frac 1 {1+A_n}$

Given : $\forall n\in\Bbb N,\quad A_{n+1} = \frac 1 {1+A_n}$ and $A_1 = 0$ Show the sequence converges and find its limit. Briefly what I did was to create two sub-sequences with an index ...
1
vote
1answer
43 views

Prove that the set of solutions to $F_{n+2} = F_{n+1} + F_n$ is of dimension 2

I was playing with the Fibonacci sequence, willing to prove that $$ F(n) = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right) $$ I did the usual, ...
1
vote
1answer
32 views

Discreet Math - Given n>= 5 how many times does fib(4) occur?

I have been trying to solve the below problem (and similar problems) but I have no clue how to tackle it. Can please help me tackle this particular problem, and how to attack similar problems? The ...
5
votes
4answers
594 views

Sum of cubes of first n fibonacci numbers

Let $\{f_k\}$ be the sequence of fibonacci numbers. It is well-known that $\sum_{k=1}^n f_k=f_{n+2}-1$ and $\sum_{k=1}^n f_k^2=f_n f_{n+1}$ . Is there a formula for $\sum_{k=1}^n f_k^3$ ?
6
votes
2answers
199 views

Sequence with denominators of products of consecutive Fibonacci numbers

I'm trying to figure out a way to solve the value of this: $$\frac{1}{1\times 2}-\frac{1}{2\times 3}+\frac{1}{3\times 5}-\frac{1}{5\times 8}+\frac{1}{8\times 13}-\dots$$ The only thing I can come up ...
1
vote
4answers
133 views

Prove that the Fibonacci recursion diverges

I have this sequence with $ n \in \mathbb{N} $ $ f(1) = f(2) = 1 $ and $ f(n) = f(n-1) + f(n-2) $ for $n \ge 3$ I think this sequence is bounded below and unbounded above. So it's clear that this ...
1
vote
1answer
37 views

Limit of Ratio of Two Generalized Fibonacci Sequences

I am hoping someone can help me determine the limit of two unique generalized Fibonacci sequences. Most everyone is familiar with the much talked about $\lim_{x\to \infty}$ ...
0
votes
2answers
28 views

Prove by induction fibonacci variation

Prove by induction: The fibonacci sequence is defined as follows: $f_1 = 1$, $f_2 = 1$ and $f_{n+2} = f_n + f_{n+1}$ for $n \geq 1$ Prove by induction that $f_1^2 + f_2^2 + \dotsb + f_n^2 = f_n ...
0
votes
2answers
54 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 ...
4
votes
5answers
94 views

Prove that $F(1) + F(3) + F(5) + … + F(2n-1) = F(2n)$

(These are Fibonacci numbers; $f(1) = 0$, $f(3) = 1$, $f(5) = 5$, etc.) I'm having trouble proving this with induction, I know how to prove the base case and present the induction hypothesis but I'm ...
2
votes
1answer
70 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 ...
1
vote
1answer
63 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. ...
2
votes
4answers
69 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
41 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: ...
2
votes
1answer
31 views

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

A mod $n$ Fibonacci sequence is simply defined as the Fibonacci 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
84 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
48 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.
8
votes
0answers
72 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
3answers
71 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 ...
0
votes
1answer
22 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
65 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 ...
5
votes
0answers
98 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 ...
1
vote
2answers
52 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 ...
8
votes
2answers
461 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
55 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
53 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 ...
19
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 ...
3
votes
3answers
39 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
47 views

Proving an equation dealing with Fibonacci numbers

Prove that: $f(2 \cdot k) = f(k) \cdot  f(k + 1) + f(k - 1)  \cdot f(k) $ Where $f(k)$ is the kth Fibonacci number. Also prove that: $f(2 \cdot  k + 1) = f(k) \cdot f(k) + f(k + 1) \cdot f(k + 1) ...
0
votes
2answers
43 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
48 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
43 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
36 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 = ...
1
vote
0answers
70 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 ...
4
votes
1answer
160 views

How many distinct ways to climb stairs in 1 or 2 steps at a time? (Fibonacci puzzle)

There is a very interesting puzzle for fibonacci sequence ...
0
votes
1answer
58 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 ...
0
votes
0answers
40 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?
4
votes
1answer
62 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 ...
3
votes
2answers
133 views

Prove the $n$th Fibonacci number is the integer closest to $\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n$

Prove that the $n$th Fibonacci number $f_n$ is the integer that is closest to the number $$\frac{1}{\sqrt{5}}\left( \frac{1 + \sqrt{5}}{2} \right)^n.$$ Hi everyone, I don't really understand the ...
0
votes
0answers
54 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?
2
votes
4answers
104 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
125 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 ...
3
votes
0answers
24 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
37 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 ...
1
vote
1answer
58 views

Calculating the hitting probability using the strong markov property

** This problem is from Markov Chains by Norris, exercise 1.5.4.** A random sequence of non-negative integers $(F)n)_{n\ge0}$ is obtained by setting $F_0=0$ and $F_1=1$ and, once $F_0,\ldots,F_n$ are ...