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

2
votes
0answers
17 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
28 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
10 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 ...
0
votes
1answer
30 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
48 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 ...
-4
votes
0answers
39 views

show $\operatorname{Fib}(n)$ is a primitive recursive function? [closed]

let $0,1,1,2,3,5,8,13,21,..$ and $\operatorname{Fib}(0)=0$ $\operatorname{Fib}(n+1)=\overline{sg}(n)+sg(n)\cdot[\operatorname{Fib}(n\dot{-}1)+\operatorname{Fib}(n)]$ show $\operatorname{Fib}(n)$ is ...
8
votes
4answers
85 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\\ ...
0
votes
0answers
26 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
37 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 ...
0
votes
1answer
52 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
2answers
61 views

Determine whether $A215928(n)=G_n$.

Let $G_0=1$ and $G_{n+1}=F_0G_n+F_1G_{n-1}+\cdots+F_nG_0$, where $F_n$ is the $n$th term of the Fibonacci sequence, i.e., $F_0=F_1=1$ and $F_{n+1}=F_n+F_{n-1}$. Let $P_0=P_1=1,\ P_2=2,$ and ...
0
votes
5answers
46 views

Prove by Induction $F_{2n} = F_{n} * L_{n}$, for n >= 1

Where $F$ is the Fibonacci Sequence, and $L$ is the Lucas Sequence. I need to find the inductive proof of this statement. I've got nearly a page of work in front of me trying to use definitions such ...
-1
votes
2answers
54 views

Mathematical induction used on Fibonacci Sequence

I have no clue how to go about doing this question using induction. It states that the Fibonacci sequence is defined as: F0 = 0 F1 = 1 Fn = Fn-2 + Fn-1 for n>=2 Let S(n) = Fo + F1 + F2 +...+ ...
0
votes
3answers
102 views

Fibonacci sequence: how does $0$ get to $1$?

In the Fibonacci sequence, how does $0$ get to $1$? $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$$ The rule is adding the previous $2$ numbers, and the previous $2$ numbers before $1$ are $0$ and ...
2
votes
0answers
55 views

Arctangents, Fibonacci numbers, and the golden ratio

In the course of doing scratchwork to answer this question, I had occasion to write the trigonometric identity $$ \arctan x- \arctan(1-x) = \arctan\left( \frac{1-2x}{x^2-x-1} \right). $$ Now notice ...
1
vote
3answers
37 views

What sequences where the difference between their consecutive terms is always a fibonacci numbers?

What sequence where the difference between its consecutive terms is always a fibonacci numbers ? I am trying to figure out a pattern in this sequence : 1,2,4,7,12,20,33,54,88
0
votes
2answers
35 views

Trouble with Fibonacci number mathematical induction

The problem is: $$F_n \leqslant 2F_{n-1}\quad\text{for every integer} \quad n \geqslant 2.$$ I got the smallest case, I just don't know how to get the assumption and the rest of it
5
votes
0answers
65 views

Legitimate papers refuting the significance of the golden ratio in art?

I'm not sure this is the right place to ask about this, but is there any legitimate peer-reviewed paper refuting the significance of the golden ratio in art? I can find numerous websites and blogs ...
4
votes
2answers
43 views

Number of Fibonacci series that contain a certain integer

In my question, I consider general Fibonacci sequences (sequences satisfying the recurrence relation $F_{n+2}=F_{n+1}+F_n$ independent of their starting value). Given two arbitrary different integers, ...
0
votes
0answers
31 views

Sum of reciprocals of (squares of) Fibonacci numbers

What would be the sum of reciprocals of all Fibonacci numbers? What about the sum of reciprocals of squares all Fibonacci numbers? This is not a homework, or something of that sort, the question ...
0
votes
2answers
30 views

Relationship between fibonacci number and modulo. [closed]

Determine with reason whether or not $$F_{5n}=0\pmod5$$ I don't have any idea about it.
2
votes
4answers
47 views

How to find closed form of summation of Fibonacci Sequence?

I created two formulas to prove a binary theory involving the Fibonacci sequence. (1) $\sum_{i=0}^n F_{2i+1} $ Equation (1) is the sum of all Fibonacci numbers up to $F_n$ where every $i$ in $F_i$ ...
0
votes
1answer
68 views

Fibonacci numeration system

Instead of binary or decimal, the Kingdom of Leutonia uses an unusual system to represent numbers, based on the Fibonacci sequence. The Fibonacci sequence $F_0,F_1,F_2,\dots$ is defined recursively ...
0
votes
1answer
38 views

Write out the Leutonian numbers that represent the first 12 positive integers.

How could I write out the leutonian numbers that represent the first 12 positive integers ? I have no idea how to start.
2
votes
1answer
58 views

determine the number of terms in a fibonacci sequence that are divisible by $3$

Consider the Fibonacci sequence $1, 1, 2, 3, 5, 8, 13, 21, . . .$ where each term, after the first two, is the sum of the two previous terms. How many of the first $1000$ terms are divisible by 3?
1
vote
2answers
104 views

Question regarding the Fibonacci sequence

Given the Fibonacci sequence $(F_1, F_2,F_3, ...)$ how do I prove that if $m|n$ then $F_m|F_n$? Can this be proven with mathematical induction?
3
votes
1answer
103 views

Powers of 2 in the product of the Fibonacci numbers

I'm working on finding a summation that pulls the powers of 2 out of the product of the Fibonacci numbers. I've noticed some patterns for the Fibonacci number. For example. Looking at the Fibonacci ...
2
votes
1answer
64 views

Are the Fibonacci numbers' prevalence in nature due to confirmation bias?

The Fibonacci numbers are frequently found in nature, such as in the petals of flowers or the shape of pinecones. But are the numbers actually any more prevalent than other numbers? Could it all be ...
5
votes
2answers
713 views

Is there among first 100000001 Fibonacci numbers one that ends with 0000?

This is a difficult problem from competition training: Is there among first 100000001 Fibonacci numbers one that ends with 0000? Trainer says use pigeonhole principle. I do not know how.
2
votes
1answer
54 views

Proving a Problem involving Fibonacci numbers

I'm working on proving the problem that states $\text {The sequence}$ {$F_n$} $\text {is defined by the} \ F_1=F_2=1, F_{n+2}=F_{n+1}+F_n \ \text {for} \ n \ge 1.$ $\text {For any natural number m, ...
1
vote
1answer
73 views

I don't know how to solve equations used in the golden ratio

Today i was reading something from golden ratio and i don't understand how some equations where solved for example: Im told that $\phi_{n+1}=B_{n+1} + \frac {A_n}{B_n}$. What I don't understand is ...
1
vote
2answers
75 views

Remarkable relation between Fibonacci numbers and its squares!

There is a remarkable relation between Fibonacci numbers and its squares: $F^{2}_{n} +F^{2}_{n+1}=F_{2n+1}$. I know how to prove it using $F_{n}=\frac{\sqrt{5}}{5}((\frac{1+\sqrt{5}}{2})^n ...
0
votes
0answers
72 views

Fibonacci sequence: Prove the formula $f_{2n+1}=f_{n+1}^2 + f_n^2$ [duplicate]

I can't seem to figure out this proof. I'm using weak induction and always get stuck during the inductive step. Prove for n > 0: $$f_{2n+1} = f_{n+1}^2 + f_n^2$$
0
votes
0answers
39 views

Count fractions between fibonacci

First a little run down on what I am doing: I have a large set of line graph data that I have collected. I've been looking at the graphs first at tick level then for the second chart I combine two ...
3
votes
3answers
60 views

When do you need to prove more than 1 base case in the Fibonacci problem?

I was trying to prove that if $F_n = F_{n-1} + F_{n-2}$ and $F_1 = 1$ and $F_2 = 1$, then the following proposition $P(n)$ was true $\forall n : \sum^n_{i=1}F_i=F_{n+2} - 1$ The issue I have with the ...
0
votes
0answers
140 views

Prime number distribution theory for dummies

For the distribution of prime numbers there is a hypothesis which predicts the possible positions of prime numbers called Riemann hypothesis ...
1
vote
0answers
27 views

How many rationals for a given $n \in \Bbb N \;\backslash \{1\}$?

Fix $n \in \Bbb N, n> 1$. Now choose a two digit base-$n$ number $ab $ say. There's $n^2$ choices for this. Consider the number $0.c_1 c_2 c_3 \ldots$ where the $c_i$ are defined recursively: ...
1
vote
1answer
39 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
2
votes
1answer
329 views

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if 1 and n also count as consecutive? It looks that the number of such subsets obeys the ...
4
votes
1answer
139 views

Relationship between Primes and Fibonacci Sequence

I recently stumbled across an unexpected relationship between the prime numbers and the Fibonacci sequence. We know a lot about Fibonacci numbers but relatively little about primes, so this connection ...
8
votes
1answer
88 views

If the generating function summation and zeta regularized sum of a divergent exist, do they always coincide?

One could assign a value to divergent series by means of several summation methods. One summation method we could consider is the generating function method. Let's sum, for example, the fibonacci ...
0
votes
2answers
54 views

Proof of the inequality $F_i<(5/3)^i$ for the Fibonacci numbers

The example states: As an example, we prove that the Fibonacci numbers, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5,..., Fi = Fi - 1 + Fi - 2, satisfy Fi < (5/3)i, for all i >= 1. To do this, we ...
5
votes
3answers
70 views

Fibonacci sequence: Given $n$ and $\mathrm{Fib}(n)$, is it possible to calculate $\mathrm{Fib}(n-1)$?

Given $n$ and $\newcommand{\Fib}{\mathrm{Fib}} \Fib(n)$, is it possible to calculate the previous number in the Fibonacci sequence - $\Fib(n-1)$ using integer math in constant time? In other words, I ...
1
vote
1answer
33 views

How do I proceed from here on finding the Binet's formula via generating functions?

So, I'm stuck with the algebra for the nth number on the Fibonacci sequence in here. I managed to get to the part where $G(x) = \frac{x}{1-x-x^2}$ $=$ $\frac{x}{(1-\alpha x)(1-\beta x)}$, and I know ...
-1
votes
1answer
68 views

using induction to prove that the formula for finding the n-th term of the Fibonacci sequence is: [duplicate]

May someone help me? I am trying to use induction to prove that the formula for finding the $n^{th}$ term of the Fibonacci sequence is: ...
3
votes
3answers
97 views

Proof by induction: $n$th Fibonacci number is at most $ 2^n$

I'm trying to find the proof by induction of the following claim: For all $n\in\mathbb N$, $\operatorname{fibonacci}(n) \le 2^n$ My Proof: Base case: $n = 1$ $\operatorname{fibonacci}(1) \le 2^ 1$ ...
1
vote
2answers
79 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
2
votes
1answer
101 views

Generalised Fibonacci

How to find the nth term of the recurrence in $\log n$ time. $$ \begin{array}{rcl} F[n]&=&F[n-1]+F[n-3]\\ F[2]&=&1\\ F[3]&=&2\\ F[4]&=&3\\ F[5]&=&4 \end{array} ...
1
vote
0answers
68 views

Sum of a Sequnce

How to find this sum $$ \sum_{i+j+k=n} \ G_i \cdot G_j \cdot G_k \ for \ all \ i,j,k > 0, $$ $$ G_i = i \cdot F_i, $$ where Fi - ith number Fibonacci, F0=0, F1=1
0
votes
3answers
74 views

Adding Fibonacci Numbers

I am getting confused on adding Fibonachi numbers. For example I know that: $\mathrm{F}_\mathrm{K+1}+\mathrm{F}_\mathrm{K}=\mathrm{F}_\mathrm{K+2}$ But I believe my logic is flawed. The way i am ...