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

Prove that $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$ [duplicate]

Prove that $F_{n}^{2}+F_{n+1}^{2}=F_{2n+1}$ This identity holds for $n>=1$ Instead of using induction, how do I prove it in a geometry approach?
4
votes
1answer
140 views

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

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?
1
vote
1answer
101 views

Prove that if $\sigma(F_a)<\sigma(F_b)$, where $1 \leq b < a$, then $\sigma(a)<\sigma(b)$ also

Prove that if $\sigma(F_a)<\sigma(F_b)$, where $1 \leq b < a$, then $\sigma(a)<\sigma(b)$ also. Here $\sigma(x)$ denotes the sum of the divisors of $x$ and $F_x$ is the $x$th Fibonacci ...
2
votes
1answer
211 views

Determine whether every characteristic factor of the nth Fibonacci number is $\equiv \pm 1 \mod n$

Determine whether all characteristic factors of the $n$th Fibonacci number, which are primes $p_1, p_2,..., p_k$ such that $p_i \mid F_n$ and $p_i \not\mid F_m \hspace{3 mm} \forall i \in [1,k], m \in ...
3
votes
1answer
63 views

Prove that $F_{x^{n+1}} \sim 5^{\frac{x-1}{2}}F_{x^n}^x \forall x,n \geq 1$, holding either variable constant while the other goes to infinity

I noticed from looking at the prime factorizations of some Fibonacci numbers that all those with an index equal to a power of 5 divided that power of five, a property not guaranteed by the strong ...
2
votes
1answer
67 views

A Generalized Fibonacci sequence

I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$. My Try: For $a=1$ this is just the Fibonacci ...
2
votes
2answers
106 views

Is Fibonacci sequence the minimum of unique pairwise sum sequence?

Let $(a_n)_{n=1}^\infty$ be a strictly increasing (condition added per earlier answer of Amitesh Datta) sequence of natural numbers where all pairwise element sums are unique. Can anyone prove or ...
6
votes
0answers
420 views

A conjecture about Lucas series

Let $L_n$ be the Lucas series: $L_0=2,L_1=1,L_n=L_{n-1}+L_{n-2}(n>1).$ $p$ is a prime number and $p\equiv3,7\pmod {20}$, hence $\exists x,y\in \mathbb Z:2p=x^2+5y^2.$ Is it true that ...
0
votes
3answers
48 views

Fibonacci terms with primal distances

Given any prime $p$, are there fibonacci numbers $F_k $ and $F_n$ such that $|F_n - F_k|=p^i , i \in \mathbb N$?
2
votes
3answers
456 views

Strong inductive proof for this inequality using the Fibonacci sequence.

Problem I need to determine for what natural numbers is $2n < F_n$, where $F_n$ is the $n^{th}$ Fibonacci number determined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1}+F_{n-2}$. I then need to ...
1
vote
1answer
93 views

Sums and products involving Fibonacci

In summary, if $\phi$ is the golden ratio, I want to show: \begin{align} \sum_{n=1}^\infty \frac1{F_n} &= 4-\phi \\ \sum_{n=1}^\infty \dfrac{(-1)^{n+1}}{F_nF_{n+1}} &= \phi-1 \\ ...
1
vote
1answer
58 views

Solving $ F_{n} = \sum_{i=1}^{n-1} (F_{i}\cdot F_{n-i}) $?

I need to find $F_{n}$ in : $$ F_{n} = \sum_{i=1}^{n-1} (F_{i}\cdot F_{n-i}) , F_0 = 0 , n>=2 $$ This equation screams convolution , I think , but I find it as a quite long solution sometimes. ...
1
vote
3answers
74 views

Find $F_{n}$ in : $F_{n} +2F_{n-1} + … + (n+1)\cdot F_{0} = 3^{n}$

I'm stuck with the question for a while : Find in $$F_{n} +2F_{n-1} + ... + (n+1)\cdot F_{0} = 3^{n}$$ the element $F_{n}$ . Placing $n-1$ instead on $n$ results in : $$F_{n-1} +2F_{n-2} + ... + ...
2
votes
1answer
64 views

Solve a recursion using generating functions?

Given the recursive equation : $$F_n+F_{n-1}+⋯+F_0=3^n , n\geq0$$ A fast solution that I can think of is placing $n-1$ instead of $n$ , and then we'll get : $$F_{n-1}+F_{n-2}+⋯+F_0=3^{n-1} $$ ...
9
votes
4answers
224 views

Fibonacci Cubes: $F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$

Prove $$F_n^3 + F_{n+1}^3 - F_{n-1}^3 =F_{3n}$$ I've tried induction, either its just very long or a neat trick is required in the inductive step but for some odd reason its not working out. ...
2
votes
2answers
637 views

Solve the recurrence of $T(n)= 3T(n-1)+1$ with$ T(0)=2$ by iteration of the recurrence

Solve the recurrence of $T(n)= 3T(n-1)+1$ with $T(0)=2$ by iteration of the recurrence. (I was told that there is no need to prove it by induction) I googled "iteration of the recurrence." I did not ...
0
votes
0answers
23 views

Solve the recurrence of T(n)= 3T(n-1)+1 with T(0)=2 as a first order linear recurrence. [duplicate]

Solve the recurrence of T(n)= 3T(n-1)+1 with T(0)=2 as a first order linear occurrence. I would do T(0)= 3T(-1)+1=2. I need to find a condition for n<0 and n>0. Any tips on getting started? ...
2
votes
3answers
509 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
2answers
107 views

Suppose that a recursive routine were invoked to calculate F(4). How many times would a recursive call of F(1) occur?

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$$ Suppose that a recursive routine were invoked to calculate $F_4$. How many times would a ...
1
vote
3answers
487 views

Prove that $F(n+3)=2F(n+1)+ F(n)$ for $n \ge 0$

The definition of a Fibonacci number is as follows: $$F(0)=0\\ F(1)=1\\ F(n)= F(n-2)+F(n-1)\text{ for }n\geq 2$$ Prove the given property of the Fibonacci numbers directly from the definition. ...
0
votes
1answer
67 views

Is the Fibonacci number-like function too trivial to investigate about?

To make some interesting recursive function, I generalized Fibonacci numbers to a function $f(x)$ such that satisfies the following condition: Given a function $g(x)$, such that $g(0)=0$ and ...
8
votes
7answers
348 views

Why is the Fibonacci ratio though a decreasing function, it is alternating and decreasing?

I tried to find the ratio of consecutive terms of the Fibonacci series and found that it is a decreasing function and it converges . I tried it though a small code piece in python so that I can have a ...
-1
votes
3answers
259 views

Show that the limit exists and find it's value? [duplicate]

The Fibonacci series defined recursively by $x(1) = 1, x(2) = 2$ and $x(n+1) = x(n) + x(n-1)$ Find$$\lim_{n\rightarrow\infty}\frac{x(n+1)}{x(n)}$$
5
votes
4answers
518 views

Is Binet's formula for the Fibonacci numbers exact?

Is Binet's formula for the Fibonacci numbers exact? $F_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n \sqrt{5}}$ If so, how, given the irrational numbers in it? Thanks.
3
votes
2answers
2k 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 ...
4
votes
0answers
62 views

A Fibonacci like Stochastic process

Let $X_0, X_1$ and $\{a_n,n\geq0\}\sim $Bernoulli$(1/2)$ taking values in $\{0,2\}$. Let us define $X_n$ for $n>1$ as below$$X_{n+1}=a_nX_n+a_{n-1}X_{n-1},\ n\geq1 $$ Then it follows that ...
6
votes
5answers
276 views

Fibonacci-like sequence

Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive ...
-1
votes
3answers
601 views

What are the first 3 digits of the product of the first 1000 fibonacci numbers

What are the first 3 digits of the product of the first 1000 Fibonacci numbers? Could anyone give me hints on how to start this problem? I haven't done a problem like this before and I am curious ...
5
votes
1answer
243 views

What is wrong with my induction proof?

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 < ...
-3
votes
2answers
309 views

on fibonacci sequence how to prove that $a_n=\frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$ [closed]

how to prove that $$a_n=\frac{1}{\sqrt{5}} ((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$$ without use induction is there any help ? thanks for all
2
votes
1answer
203 views

Seeking a combinatorial proof of the Fibonacci identity $f_{2k-1}f_{4k}=f_{2k}+f_{2k}f_{4k-1}$

I would appreciate if somebody could help me with the following problem Q: Show that (for $k,n\in \mathbb{N}$), if $f_1=f_2=1$, $f_{n+2}=f_{n+1}+f_n$, then ...
2
votes
5answers
769 views

What is the summation notation for the Fibonacci numbers?

I learned about summation notation the other day, and I'm looking for a way to write the Fibonacci numbers with it. What would it look like?
0
votes
3answers
82 views

Fiddling with a Fibonacci-Like Sequence

Let $X\in\mathbb{Z}.$ Let $F_n$ be a sequence of positive integers given by $$F_{i+1}=F_i+F_{i-1}$$ $$F_2=X*F_1+F_0$$ I am trying to find an upper bound or (sharp) inequality of $F_i$ in terms of ...
6
votes
2answers
95 views

Error in Fibonacci recurrence proof by induction?

I'm working on a problem from a number theory book (Number Theory by George E. Andrews - problem 1-1-11). The text reads: Prove: $\displaystyle F_1F_2+F_2F_3+F_3F_4+\ldots+F_{2n-1}F_{2n}=F_{2n}^2$ ...
3
votes
3answers
110 views

Fibonacci sequence: how to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$?

Let $F_n$ be the $n$th Fibonacci number. Let $\alpha = \frac{1+\sqrt5}2$ and $\beta =\frac{1-\sqrt5}2$. How to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$? I'm completely stuck on this question. ...
3
votes
1answer
96 views

Have I correctly derived an inverse to the Binet formula?

I was interested by another user's question on finding such an inverse and in particular noted Will Orrick's comment in the best answer that one can square both sides to obtain a quartic.I thought I'd ...
2
votes
1answer
112 views

Important numbers in Combinatorics

I recently went through some important numbers like the Stirling and Bell number for calculation of partitions /equivalence relations. I was wondering if someone can help me get a list of important ...
3
votes
1answer
112 views

Invent a combinatorial interpretation for the ''Tribonacci numbers''

" Recall that our combinatorial interpretation of the Fibonacci numbers $f_0 = f_1 = 1$ with $f_n = f_{n-1} + f_{n-2}$ for $n \geq 2$ was the number of ways to tile a board of length $n$ using squares ...
2
votes
3answers
106 views

How to prove? (Do not use mathematical induction)

I would appreciate if somebody could help me with the following problem: Q: Show that $$f_1=f_2=1, f_{n+2}=f_{n+1}+f_{n}(n\in \mathbb{N})~~~~ \Rightarrow ...
0
votes
2answers
122 views

intuition for the closed form of the fibonacci sequence

I'm trying to picture this closed form from Wikipedia visually: The idea is, if you take $\phi^n / \sqrt{5}$ and round it to the nearest integer, you'll get the $n$th Fibonacci number. I see ...
2
votes
2answers
365 views

How do I prove Binet's Formula? [duplicate]

My initial prompt is as follows: For $F_{0}=1$, $F_{1}=1$, and for $n\geq 1$, $F_{n+1}=F_{n}+F_{n-1}$. Prove for all $n\in \mathbb{N}$: ...
3
votes
2answers
84 views

What is the functional inverse (with respect to $h$ (!)) of $f^{\circ h}(x)={F(h) +x F(h-1) \over F(1+h) +x F(h) }$?

I've considered the fractional iteration of $f(x) = {1 \over 1+x} $ for which the general expression depending on the iteration-height parameter $h$ might be assumed by the formula $$ f^{\circ h}(x) ...
1
vote
1answer
62 views

What is the broader name for fibonacci and lucas sequences?

Fibonacci and Lucas sequences are very similar in their definition. However, I could just as easily make another series with a similar definition; an example would be: $$x_0 = 53$$ $$x_1 = 62$$ $$x_n ...
1
vote
1answer
114 views

Register Machine on Fibonacci Numbers

This problem is easy to understand but I am struggling to come up with any solutions. According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a ...
1
vote
2answers
365 views

proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3

I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers: $$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
1
vote
2answers
120 views

Induction on the Fibonacci sequence?

Prove by induction that the $i$th Fibonacci number satisfies the equality: $$F_i = \frac {\phi^i - \hat\phi{}^i}{\sqrt5}$$ where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate. ...
7
votes
2answers
127 views

Fiboncacci theorem: Proof by induction

I have the following theorem to prove by induction: $$ F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$ It is mentioned in my script that the proof should be possible only by using the ...
2
votes
2answers
300 views

How can I find an inverse to the Binet formula?

I'm already aware of the Binet formula $F_n = \frac{\varphi^n + \frac{1}{\varphi^n}}{\sqrt{5}}$. I'm attempting to find the inverse of that formula so I can find the position in the sequence of ...
1
vote
3answers
237 views

Proof of identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ for Fibonacci numbers

I'm lost on where to start on this proof: Using the fact that $A^m A^n = A^{m+n}$ , prove the identity $F_m F_n + F_{m−1} F_{n−1} = F_{m+n−1}$ I want to use induction starting with n = 1, but would ...
1
vote
0answers
64 views

Simplify Fibonacci Power Series

I am working on an algorithm to count the number of models for Exactly One in Three SAT (X3SAT) instances. It is known that a chain of X3SAT clauses of length $c$ has $F(c+3)$ satisfying assignments ...