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

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
35 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
634 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
208 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
146 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
39 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
35 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 ...
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 ...
4
votes
5answers
98 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 ...
3
votes
1answer
79 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
70 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
73 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
46 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
32 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
98 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
50 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
74 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
73 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
25 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
66 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 ...
6
votes
1answer
138 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 ...
2
votes
2answers
55 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
566 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
63 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$.
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 ...
1
vote
1answer
57 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
42 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
49 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
46 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
71 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
229 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
64 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 ...
2
votes
2answers
149 views

Show that Fibonacci and Lucas numbers satisfy the following equality for all n ≥ 2.

Fibonacci numbers F1, F2, F3, . . . are defined by the rule: F1 = F2 = 1 and Fk = Fk−2 + Fk−1 for k > 2. Lucas numbers L1, L2, L3, . . . are defined in a similar way by the rule: L1 = 1, L2 = 3 and ...
0
votes
0answers
48 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
68 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
181 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
57 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
112 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
128 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
25 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
38 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
69 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 ...
2
votes
1answer
44 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
71 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 ...
9
votes
4answers
100 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\\ ...
2
votes
2answers
126 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. ...