Questions tagged [fibonacci-numbers]

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$.

Filter by
Sorted by
Tagged with
2
votes
1answer
19 views

Convergence in the Generalized Fibonacci Sequence to the golden ratio

Many posts have shown the convergence of the ratio of two consecutive terms in the Fibonacci sequence $F_{n+1} = F_n + F_{n-1}$ when the starting values are $F_0 = 0$ and $F_1 = 1$. How do we show ...
0
votes
1answer
34 views

Trying to prove by induction that $\sum_{i=1}^{k} F_{2i}=F_{2k+1}-1$ for all $k∈N$

I am trying to prove by induction the following proposition of the fibonacci sequence: The fibonacci sequence is defined recursively as: $f_1 = 1$, $f_2 = 1$, and that for all integers $k>=1$, $f_{...
1
vote
2answers
29 views

Prove $F_n=(-1)^{n+1}F_{-n}$ without induction

Consider the Fibonacci sequence defined by $$F_{n+2}=F_{n+1}+F_n,~~~~~~F_1=F_2=1$$ I can prove via induction that $F_n=(-1)^{n+1}F_{-n}$, but how can it be proven without using induction? Thank you ...
0
votes
1answer
42 views

Induction proof on Fibonacci sequence [closed]

I'm unsure how to use induction to solve this problem. The question asks: Let $F_n$ be the $n$-th Fibonacci number, where $F_{n+1} = F_n+F_{n−1},\, F_0 = 1,\, F_1 = 1$ and $n$ is a natural number. (a) ...
10
votes
4answers
2k views

Does the order of the Fibonacci sequence's initial values matter?

I am reading about generating functions in this reputable engineering textbook and the author uses the Fibonacci sequence as an example: The Fibonacci sequence is defined by the initial conditions $...
0
votes
0answers
38 views

Proof of sum of ratio of Fibonacci numbers is less than 2 [duplicate]

Using notation $F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, ...$ for Fibonacci numbers prove that for any positive integer $n$: $$\frac{1}{1\cdot 2} + \frac{2}{1\cdot 3} + \frac{3}{2 \cdot 5} + · · · ...
-5
votes
0answers
63 views

Generalizations of Fibonacci numbers [closed]

I came to this conclusion about "the golden number".A simple generalization for the golden number. My question : Is there a better generalization than this ? i need to know it. and thank ...
2
votes
1answer
54 views

Prove 1 + 4 Product of fibonacci numbers is a perfect square

Let $n \in \mathbb N$ . Prove that $1 + 4 F_{2n}F_{2n+1}F_{2n+2}F_{2n+3}$ is the square of an integer. I first tried to used Cassini's identities but failed.I tried then by induction and again failed....
2
votes
1answer
38 views

Prove that the data given produce the fibonnaci sequence if that is indeed the solution

I am looking into the following puzzle: Male bees hatch from unfertilized eggs and so have a mother but no father. Female bees hatch from fertilized eggs. How many ancestors does a male have in the ...
0
votes
0answers
28 views

If $a_n$ is the $n$th term of the Fibonacci sequence, then prove that $a_{n+1}^2 - a_n a_{n+2} = (-1)^n$. [duplicate]

This, I think uses induction. I simplified the equation to get $a_{n+2}.a_{n-1} - a_n(a_n + 1) = -1^n$ This might not be simplifying it at all. Also, I noticed that at $n+1$, R.H.S. becomes$-1^{n+1}= -...
0
votes
2answers
107 views

Find all $n!$ that are products of two Fibonacci numbers

Find all positive integers $n$ such that $n!$ is the product of two Fibonacci numbers I found this discussion, but it doesn't quite help my problem. Check if the number is a result of multiplying two ...
0
votes
2answers
51 views

Let $a_1=a_2=1$, $a_3=2$ and $a_n=a_{n-1}+a_{n-2}$ for $n\ge3$. Prove that $a_1 + a_2 + \ldots + a_n = a_{n+2} - 1$. [duplicate]

I think that this needs the use of a strong form of induction. So, I tried it with $k$ $3\le k\le n$, where $n$ is arbitrarily chosen. But I can't proceed beyond this.
1
vote
0answers
28 views

Continous extension of Fibonacci numbers [duplicate]

If we consider the sequence $a_n = (n-1)!$ then the Gamma function $\Gamma(n)$ gives exactly $a_n$ at each positive integer $n$. Let $F_n$ denote $n^{th}$ Fibonacci number. Does there exist a ...
0
votes
0answers
34 views

Recurrence relations and generating functions

Q. Solve the following recurrence relation with the initial conditions: $a_n=a_{n-1}+a_{n-2}$ for $n\ge2,$ and $a_0=0,a_1=1.$ I started with $G(x)=\displaystyle\sum_{n=0}^{\infty}a_nx^n,$ and after ...
2
votes
1answer
42 views

Relation between cubes of Fibonacci numbers and even Fibonacci numbers

While recently revisiting an old Project Euler problem, which states: Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 ...
1
vote
1answer
26 views

Fibonacci sequence proof.

Given the Fibonacci Sequence $F_{0}=0,F_{1}=1,F_{n+2}=F_{n+1}+F_{n+1};\;n\geq0$ Prove the following: $\sum_{i=1}^{n}\frac{F_{i-1}}{2^{i}} = 1-\frac{F_{n+2}}{2^{n}}$ Base case: $\frac{F_{0}}{2^{0}}= 1-\...
1
vote
2answers
32 views

Fibonacci sequence proof, how should I proceed? [duplicate]

Given the Fibonacci sequence $F_{0}=0 \;,\; F_{1}=1 \;,\; F_{n+2}= F_{n+1}+ F_{n+1} ; \;\; n\geq 0$ Prove that $ \sum _{i=1}^{2n}F_{i}F_{i-1} = F_{2n}^{2}\\$ Base Cases: $ F_{1}F_{0} = F_{0}^{2}\\...
7
votes
1answer
135 views

If $\left\{a_n\right\}$ is Fibonacci Number, prove that the sequence$\left\{\frac{\ln a_n}{\ln a_{n+1}}\right\}$ increase

If $a_0=1,a_1=1,a_{n+2}=a_{n+1}+a_{n}$, prove the sequence$\left\{\frac{\ln a_n}{\ln a_{n+1}}\right\},\,n\geq 1$ increase. When $n$ is even this inequality is easy proved by Am-Gm. If $n$ is even,we ...
-3
votes
0answers
65 views

Distribution of Prime numbers between Fibonacci numbers. How to prove my hypothesis for much higher values, for ex. Fib(250) and Fib (251)?

I have drawn Fibonacci spiral with indicated prime numbers. My research shows interesting dependency between Primes and Fibonacci numbers. Let us treat the successive Fibonacci numbers as the limit ...
3
votes
1answer
68 views

What's the necessary and sufficient condition of $p^m|F_n$?

Let {$F_n$} be Fibonacci Series defined by $F_{n+2}=F_{n+1}+F_n$ with $F_1=F_2=1$.I have proved that $3^m|F_n \Leftrightarrow 4\cdot 3^{m-1}|n$ for another problem.Then I began to think about the ...
2
votes
1answer
53 views

Lucas Number Sequence Theorem

How can I prove the following theorem using Induction about Lucas Numbers: $$a_{2n} = a_{n} \, b_{n}$$ Here, $a_{n}$ is the Fibonacci Sequence and $b_{n}$ is the Lucas Sequence. I tried to prove it ...
-3
votes
1answer
61 views

Proving the Fibonacci identity $a^2_{n+1} - a_{n}a_{n+2} = (-1)^n$ using mathematical induction [closed]

Prove by Mathematical Induction that: $$a^2_{n+1} - a_{n}a_{n+2} = (-1)^n$$ Here the terms are from the Fibonacci Sequence.
0
votes
1answer
34 views

Last Digit of the Sum of Fibonacci Numbers

I want to calculate the last digit of a sum of Fibonacci numbers: $F_{m} + F_{m + 1} + \cdots + F_{n}$. $m$ and $n$ are $2$ non-negative integers and $m \leq n$. I have one sample input with output $...
1
vote
1answer
47 views

BlackWhite mathematics

I got this question: In the famous Atlantis city BlackWhite the houses have five levels and each level is painted either by black or by white paint, but two adjacent floors can’t be both black or ...
1
vote
2answers
61 views

Fibonacci variant with small exponent

The standard Fibonacci sequence defined by $F(n) := F(n-1) + F(n-2)$ has exponential asymptotic growth as stated e.g. here (with the approximate base being the golden ratio). What happens if the ...
1
vote
1answer
39 views

Why is there a second basis step for k = 2 in this problem?

I'm new to forum-posting, and apologize in advance for poor formatting. I'm a bit confused on a proof involving Strong Induction and Fibonacci numbers, which displays as an image here (apologies again ...
1
vote
3answers
55 views

Closed form for $\sum_{k=0}^{n}\left(-1\right)^{k}F_{k}^{2}$

How to get a closed form for the following sum: $$\sum_{k=0}^{n}\left(-1\right)^{k}F_{k}^{2}$$ Where $F_k$ is the $k$th Fibonacci number. I tried to get a recurrence relation,but I failed and the ...
0
votes
1answer
49 views

Sum of Fibonacci reciprocals converges

There are already proofs for this on Stackexchange, but I am seeking a specific one I am interested in. Let $\{u_k\}^\infty_{k=0}$ be the Fibonacci sequence, where $u_0=u_1=1$ and $u_{k+1}=u_k+u_{k-1}$...
2
votes
0answers
30 views

Intersection of two homogeneous linear second-order recurrence sequences with constant coefficients

Say we are given two sequences $u_n$ and $v_n$, defined by the following homogeneous second-order recurrence relations: $$u_n=3u_{n-1}-u_{n-2}$$ $$v_n=3av_{n-1}-v_{n-2}$$ where $a$ is a constant and $...
0
votes
1answer
94 views

Contest Problem linked to Fibonacci and Number Theory

Consider the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, ... What are the last three digits (from left to right) of the 2020th term? I tried using formulae for nth term of Fibonacci series using ...
0
votes
1answer
37 views

Time Complexity through recurrence relation

Suppose I have a code whose runtime complexity is described as a second degree linear homogeneous recursion formula as fn = fn−1 + fn−2, n>=3 where f1 = 1 and f2 = 2. I want to find constant c such ...
-1
votes
1answer
75 views

In the Fibonacci sequence, how do you prove that $(F_n)^2 + (F_{n+1})^2= F_{2n+1}$? [closed]

In the Fibonacci sequence, how do you prove that $(F_n)^2 + (F_{n+1})^2= F_{2n+1}$? Can this be done without induction or matrices? If so please demonstrate, I have been looking for a week and I still ...
1
vote
2answers
49 views

If $f_n$ is the $n$th Fibonacci number then $\lim_{n\to \infty} (f_{n-2}+{1-\sqrt 5\over 2}f_{n-1})$?

If $f_n$ is the $n$th Fibonacci number then what is the value of $$\lim_{n\to \infty}\left(f_{n-2}+{1-\sqrt 5\over 2}f_{n-1}\right)?$$ With direct calculation I saw the first four terms are ...
1
vote
0answers
25 views

Dedekind sums when h,k are from Fibonacci sequence

This is definition of dedekind sums : https://mathworld.wolfram.com/DedekindSum.html Let {u(n)} be fibonacci sequence such that u(1)=u(2)=1 and u(n+1) = u(n)+u(n-1). If h=u(2n) and k=u(2n+1) then ...
14
votes
1answer
192 views

Fibonacci numbers in two sets

Is there a way to split all natural numbers (without zero) into two sets, so that no two elements in the same set add up to a Fibonacci number? I made a c++ program and it worked for the first 100'000 ...
0
votes
2answers
56 views

Zeckendorf with Negative Fibonacci Numbers

Zeckendorf : Every positive integer N can be expressed uniquely as a sum of distinct non-consecutive Fibonacci numbers I was wondering if this theorem can be applied with the extended Fibonacci ...
2
votes
0answers
57 views

Maximum Pisano Periods

Let $\{F_i\}_{i\geq 0}$ denote the Fibonacci sequence, where $F_0=0$, $F_1=1$, and $F_{i+1}=F_i+F_{i-1}$ for $i\geq 1$. Let $p$ be an odd prime number. The Pisano period $\pi(p)$ is the least positive ...
1
vote
1answer
134 views

A prime problem in Fibonacci sequence

This problem can be a little too wild but have at it anyways: Prove that for every positive integer $n$ $\geqslant$ $7$ , $f_{n+1}$ has a prime divisor that doesn't divide $f_{n}-1$ where $f_{n}$ is ...
9
votes
2answers
255 views

How to show that $\frac{a + b}{\gcd(a,b)^2}$ is a Fibonacci number when $ \frac{a+1}{b}+\frac{b+1}{a}$ is an integer?

Let $a, b$ be positive integers such that the number $ \dfrac{a + 1}{b} + \dfrac{b + 1}{a}$ is also integer. Then, show that $\dfrac{a + b}{\gcd{(a, b)^{2}}}$ is a Fibonacci number. I prove that : $ \...
0
votes
1answer
37 views

$f_0 = 0$,$f_1= 1$, and $f_n=f_{n-1}$ + $f_{n-2}$, for all $n>=2$. Use mathematical induction to prove

$\sum_{i=0}^{2n}(-1)^i f_i = f_{2n-1} - 1$, for any positive integer n. Let P(n) be $\sum_{i=0}^{2n}(-1)^i f_i = f_{2n-1} - 1$. Basis step P(1) : $\sum_{i=0}^{2}(-1)^i f_i = f_{2*2-1} - 1$. 1=1 =&...
1
vote
1answer
60 views

Recurrence Relation General Formula Using Power Functions

Several sources propose finding a general formula for the $n^{\text{th}}$ term of a sequence defined by a recurrence relation by assuming the term is defined by a power function. E.g. consider the ...
1
vote
1answer
34 views

$F_k|F_n$ given $k | n$

Problem: Given $n, k \in \mathbb{N}$ such that $k | n$, show that $F_k|F_n$. My attempt: We have that $F_n = |\tau_{n-1}|$ where $|\tau_{n-1}|$ represents the number of ways to tile a row of $n-1$ ...
2
votes
0answers
76 views

Study the convergence of $u$ such that $u_{n+2} = \frac{u_n u_{n+1}}{n}$

The exercise Let $s > 0$, study the convergence of $u \in \mathbb{R}^{\mathbb{N}^\star}$ such that $u_1=1, u_2 = s$ and $u_{n+2} = \frac{u_n u_{n+1}}{n}$ for all $n \geq 1$. My try Clearly, $u$ is ...
4
votes
2answers
146 views

Solving finite and infinite nested square roots of 2 - yet another interesting approach

Consider the following consecutive equalities: $\sqrt2=2\cos(\frac{1}{4})\pi$ $\sqrt{2-\sqrt2}=2\cos(\frac{3}{8})\pi$ $\sqrt{2-\sqrt{2-\sqrt{2}}}=2\cos(\frac{5}{16})\pi$ $\sqrt{2-\sqrt{2-\sqrt{2-\sqrt{...
3
votes
0answers
82 views

A PigeonHole principle (combinatorics)problem using Fibonacci numbers [duplicate]

Define the sequence of Fibonacci numbers as: $F_1$ = $F_2$ = 1 and $F_n$ = $F_{n−1}$ + $F_{n−2}$ for every n > 2. Prove that, for any positive integer $k$, there is a Fibonacci number ending with $...
1
vote
3answers
92 views

How do I prove $\frac{f_{2n+1}}{f_{2n}}>\frac{f_{2n}}{f_{2n-1}}$?

How do I prove this inequality with sequential Fibonacci numbers: $\frac{f_{2n+1}}{f_{2n}}>\frac{f_{2n}}{f_{2n-1}}$ (i.e. $\frac{5}{3}>\frac{3}{2}$)? I know these formulas alternately ...
2
votes
2answers
54 views

What is the name of Fibonacci variation when $F(n) = a\cdot F(n-1) + b\cdot F(n-2) + c$, were $c$ is a constant, and $a >0, \ b >0, \ c>0$

I am trying to write $\log(n)$ algorithm for the above. I don't know if there is a specific name for the Fibonacci variation when: $$F(n) = a\cdot F(n-1) + b\cdot F(n-2) + c$$ where: $a >0, \ b >...
3
votes
1answer
132 views

Evaluating the sum $\sum_{n=1}^{\infty}\frac{1}{F_n}$

Let $F_n$ be the $n^\text{th}$ Fibonacci number. I wanted to calculate $$\sum_{n\ge1}\frac{1}{F_n}$$ I simplified it to $$\sqrt{5}\sum_{n\ge1}\frac{1}{\varphi^n-\phi^n}$$ But this didn't seem to help....
2
votes
1answer
52 views

nth Fibonacci number divided by 2 to the n

Is there any way to calculate $\sum_{n=1}^{\infty} \frac{F_{2n}}{2^{2n}}$ where $F_n$ is the nth Fibonacci number, $F_1=0$, $F_2=1$, $F_n = F_{n-1} + F_{n-2}$
1
vote
2answers
52 views

Induction to prove Fibonacci's sequence grows exponentially fast [duplicate]

How to solve this using induction? Use induction to prove that $F_n\ge2^{\frac n2}\;,\;$ for $n\ge6\;.$ $F_0=0\;,\;F_1=1\;,\;F_n=F_{n-1}+F_{n-2}\;.$

1
2 3 4 5
38