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

0
votes
1answer
75 views

Fibonacci polynomials

The Fibonacci polynomials are defined by the recurrence relation: $$ F_{n+1}(x)=xF_{n}(x)+F_{n-1}(x)\, . $$ with $F_1(x)=1$ and $F_2(x)=x$. How can I prove: $$ F_n(x)=\sum_{j=0}^{\lfloor \frac{n-1}{2} ...
9
votes
1answer
254 views

Number of ways to write $n$ as sum of odd or even number of Fibonacci numbers

In our discrete mathematics exercises I came of with the question: Prove that the coefficients of $\prod_{n\geq2}{(1-x^{F_n})}=1-x-x^2+x^4+x^7+\dots$ can only be $-1,1$ or $0$, where $F_n$ ...
-1
votes
2answers
60 views

How can I prove by induction that this is a closed form of the Fibonacci sequence? [duplicate]

How can I prove by induction that this is a closed form of the Fibonacci sequence? $$F_n=\frac1{\sqrt5}\left(\frac{1+\sqrt5}2\right)^{n+1}-\frac1{\sqrt5}\left(\frac{1-\sqrt5}2\right)^{n+1}$$ I've ...
1
vote
1answer
127 views

Formula for fibonacci(a+b).

Is there any general formula for fibonacci(A+B)? I have tried to derive it , and got following results. $$\begin{align} &fib(a+1)=1*fib(a)+fib(a-1)\\ &fib(a+2)=2*fib(a)+fib(a-1)\\ &fib(a+...
2
votes
2answers
97 views

Fibonacci Numbers and Legendre symbol

How to prove congruence below ? $$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$ Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.
0
votes
3answers
69 views

Prove by induction that the Fibonacci sequence $≤ [(1+\sqrt{5})/2]^{n−1}$, for all $n ≥ 0$.

If $F(n)$ is the Fibonacci Sequence, defined in the following way: $$ F(0)=0 \\ F(1)=1 \\ F(n)=F(n-1)+F(n-2) $$ I need to prove the following by induction: $$F(n) \leq \bigg(\frac{1+\sqrt{5}}{2}\...
0
votes
1answer
100 views

Fibonacci relation formula

There are three numbers a,b,c such that c=a+b. Let f(n) be n'th Fibonacci number,can we write f(a)+f(b) in terms of f(c) and c. If yes,how? I have tried deriving it using Binnets formula but did'nt ...
0
votes
1answer
145 views

Can the sum of different sets Fibonacci numbers be the same?

Is it possible to have two sets having at least one different element and the sum of Fibonacci of all elements be the same? As in, two subsets: ...
0
votes
1answer
76 views

Partition function and Fibonacci n-th number upperbound

i need to proof this upperbound: "Call $p(n)$ the number of partitions of n (integer) and $F_n$ the $n-th$ Fibonacci number. Show that $p(n)\leq p(n-1) + p(n-2)$ and that $p(n)\leq F_n$ for $n\geq 2$"...
4
votes
1answer
68 views

The 9 most significant digits in Fibonacci series (Project Euler 104)

With regards to project Euler, problem 104: https://projecteuler.net/problem=104 The essence of the question here is how to keep track of the 9 most significant digits of a Fibonacci series (Keeping ...
3
votes
1answer
1k views

Find the sum of Fibonacci Series

I have given a Set A i have to find the sum of Fibonacci Sum of All the Subset of A ...
2
votes
1answer
129 views

Calculating Irrationals raised to some Power modulo 1000000007 [closed]

Lets define a function F as $F(n) = 1+(\frac{1+{\sqrt 5}}{2})^n$ As per wolfram site, ${\sqrt 5}\%99991=10104$ As per wolfram site, ${\sqrt 5}\%1000000007=no\_solution$ I need to find the value of $F(...
2
votes
1answer
147 views

Relation between Fibonacci Numbers [closed]

Is there any relation between $f(a), f(b)$ and $f(a+b)$ where $f(n)$ is the $n$'th fibonacci number?
3
votes
1answer
89 views

Is there a number besides $\phi$ that either squared or added one gives the same answer?

Those who know golden ratio $\phi$ (phi) constant, know for sure that it is an interesting constant. It is roughly $\phi=1.618034...$ . It is present almost everywhere in nature and it has many very ...
1
vote
0answers
13 views

Potential Function Runtime

The potential function of a Fibonacci Heap is Φ(H) = t(H) + 2m(H) CLRS states in Figure 21.2 ...
0
votes
1answer
60 views

Interesting question on Fibonacci numbers. [duplicate]

Ran across this interesting question about the Fibonacci numbers but quite unsure how to go about it, any ideas ?
1
vote
1answer
34 views

Weird informatic problem with Fibonacci numbers in which I have some troubles

I don't know what happended to this website but for months I am not able to connect me in it. As I understand it the website is closed. It is in this website I found this problem. Let $L$ be ...
0
votes
1answer
44 views

Proof a formula of the Fibonacci sequence with induction

It turns out that the Fibonacci sequence satisfies the following explicit formula: For all integers $F_{n} ≥ 0$, $F_{n} = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n+1} - (\frac{1-\sqrt{5}}{2})^{n+1}...
8
votes
2answers
850 views

Sum of inverse of Fibonacci numbers

If $F(n)$ is the nth Fibonacci number, How can I prove that: $$\sum_{i=1}^{\infty} \frac{1}{F(i)}\approx 3.36\, .$$
0
votes
1answer
28 views

Use partial fractions to write $\frac{1}{x^2 + x – 1}$ as $\frac{A_1}{x – α_1} + \frac{A_2}{x – α_2}$ and write it as a power series

Find the roots $α_1$, $α_2$ of $x^2 + x – 1$ and use partial fractions to write $\frac{1}{x^2 + x – 1}$ as $\frac{A_1}{x – α_1} + \frac{A_2}{x – α_2}$ , for suitable $A_1, A_2$. Using the power series ...
0
votes
2answers
38 views

Prove that $\frac{a_{n+1}}{a_n}<2$ for every n>1 using induction

Fibonacci sequence of $a_n$: Prove that $\frac{a_{n+1}}{a_n}\leq2$ for every $n\geq1$. I was able to prove this using the base case: $$n=1 | n=2$$ $$\frac{a_{n+1}}{a_n}\leq2|\frac{a_{n+1}}{a_n}\leq2$$...
4
votes
1answer
56 views

Can $F_n^2-F_m^2$ be factored as a product of Fibonacci or Lucas numbers when $n-m$ is odd?

The Fibonacci and Lucas numbers are defined for all integers $n$ by the recurrence relations $$F_n=F_{n-1}+F_{n-2}\text{ where }F_1=1\text{ and }F_2=1,$$ $$L_n=L_{n-1}+L_{n-2}\text{ where }L_1=1\text{ ...
0
votes
2answers
46 views

Prove that $F_nF_{n+1}=\frac{1}{4}(F_{n+2}^2-F_{n-1}^2)$

The Fibonacci and Lucasnumbers are defined for all integers $n$ by the recurrence relations $$F_n=F_{n-1}+F_{n-2}\text{ where }F_1=1\text{ and }F_2=1,$$ $$L_n=L_{n-1}+L_{n-2}\text{ where }L_1=1\text{ ...
0
votes
2answers
51 views

Variations on Fibonacci Sequence

Do mathematicians use variations on the Fibonacci sequence? I'm thinking specifically about something like this: Start with three $1s$ and for each consecutive number, add the three previous number ...
1
vote
1answer
20 views

Is $\sum_{n,m \geq 0} F_n^m x^n y^m$ a rational generating function?

I am curious if the generating function defined by: $$ F(x,y)=\sum_{n=0}^{\infty} \sum_{m=0}^{\infty} F_{n}^m x^n y^m$$ where $F_n$ is the $n$th fibonacci number, is a rational function. That is, Is ...
1
vote
2answers
28 views

General solution expressed in $a_0$ and $a_1$ of a Fibonacci-like sequence?

What is the general solution expressed in $a_0$ and $a_1$ of a Fibonacci-like sequence ? I mean if $a_0,a_1$ are given and $a_{n+1}:=a_n+a_{n-1}$ $(\begin{array}{cc}a_n&a_{n-1}\end{array})=(\...
4
votes
1answer
62 views

Proof Fibonacci derivation

I was wondering how to prove that $$f(n+m+2) = f(n+1)f(m+1) + f(n)f(m)$$ where $f$ is the fibonacci sequence and n, m are positive integers. Can be this done with induction? I'm lost with this ...
2
votes
0answers
23 views

fibonacci recurrence problem. [duplicate]

The Fibonacci numbers Fn are defined by the recurrence Fn=Fn−1+Fn−2, with base cases F0=0 and F1=1. Prove that any non-negative integer can be written as the sum of distinct and non-consecutive ...
0
votes
1answer
30 views

Fibonacci n-step numbers

I have searched the web for a definition and I found that this are typically defined as $F^n_{m} = F^n_{m-1} + F^n_{m-2} + \dots + F^n_{m-n}$ where $n$ stands for the number of previous numbers who ...
0
votes
1answer
38 views

Reference request for a divisibility property of Fibonacci numbers

Define the Fibonacci numbers $F_n$ by $F_n=F_{n-1}+F_{n-2}$ and initial values $F_0=0$ and $F_1=1.$ I would like to get a reference for the following result: If $p$ is a prime number with $p \equiv ...
8
votes
2answers
108 views

Why do ratios of these Fibonacci-type sequences approach $\pi$?

Define $A_n$ by $A_1=12$, $A_2=18$, and $A_n=A_{n-1}+A_{n-2}$ for $n\ge3$. Similarly define $B_n$ by $B_1=5$, $B_2=5$, and $B_n=B_{n-1}+B_{n-2}$ for $n\ge3$. Terms of $A_n$: $12, 18, 30, 48, 78,\dots$...
2
votes
2answers
62 views

Prove that for all $n \geq 1$, $F_{-n}$ = $(-1)^{n+1}F_n$ where F is the Fibonacci numbers.

Prove that for all $n \geq 1$, $F_{-n}$ = $(-1)^{n+1}F_n$ where F is the Fibonacci numbers. I've already shown that the formula holds for $n = 1$ and $n = 2$. So I supposed the formula holds for $n$ ...
0
votes
1answer
41 views

Sum of digits of Fibonacci number a perfect square

During my problem solving with Fibonacci numbers following thought crossed my mind. How many Fibonacci numbers are there such that sum of its digits is a perfect square? Here is a list of ...
0
votes
1answer
55 views

Find a generating function with Fibonacci

$$G(x) = \sum_{n=1}^\infty na_n x^n $$ Hello. I need to find a generating function for the summation above, where $a_n$ is the Fibonacci sequence. I have found the generating function for the fib ...
1
vote
4answers
64 views

Basic Discrete Mathematics Recurrence question

Good afternoon, I've been assigned the following problem from my Intro to Discrete Mathematics: Show that $\sum_{i=1}^n$ F(i) = F(n+2) - 1 note: F(n) is the nth term in the fibonacci sequence. I'...
0
votes
1answer
107 views

Greatest Common Divisor with Fibonacci Numbers [duplicate]

Prove that for all integers $n\geq 0$: $$\gcd(F_{n+1},F_n)=1$$ I am extremely lost. Please can some provide some hint or direction? Thank you so very much
-2
votes
4answers
45 views

Fibonacci Numbers Induction?

Show that $a_n=n^2+n+1$ satisfies \begin{cases} a_0=1\\ a_k=a_{k-1}+2k & \text{for $k>0$} \end{cases} I want to use induction to solve this problem. but I don't know what my base will be ...
0
votes
1answer
61 views

Fibonacci-like formula for Padovan sequence

For the Fibonacci sequence, one can show the following and easy to calculate equation : $$\forall n\in \mathbb Z,~\mathcal F_n=\mathcal F_{\lfloor\frac{n}{2}\rfloor+1}^2-(-1)^n\mathcal F_{\lfloor\frac{...
0
votes
1answer
55 views

Prove fibonacci with matrixes [duplicate]

I have a question which i could not figure out the answer to, it was the hardest of them all that i got and i couldnt figure it out, its a proof of fibonaccis serie using matrixes and i need som help ...
2
votes
3answers
57 views

Proof with Fibonacci Sequence

I was working on my homework assignment for one of my classes and I have come across a proof question that my classmates and I are finding difficult to answer. The problem is asking us to prove that ...
1
vote
1answer
38 views

How to show this Fibonacci identity? $f_{3n}=f^3_{n+1} + f^3_n - f^3_{n-1}$

I already know that $f_{n+m}=f_{n-1}f_m + f_nf_{m+1}$. By letting $m=n$ it immediately follows that $f_{2n}=f_{n}(f_{n+1} + f_{n-1})$ and from that we get $f_{2n}=f^2_{n+1} - f^2_{n-1}$. From this ...
4
votes
1answer
258 views

Fibonacci sequence in the factorization of certain polynomials having a root at the Golden Ratio

I was playing around with the Golden Ratio $\Phi = \frac{1 + \sqrt 5}{2}$ on Wolfram Alpha and I noticed that if $F_n$ denotes the $n{th}$ Fibonacci number, then the polynomial $P_n(x) = x^n - F_n x - ...
1
vote
0answers
30 views

How to make inductive step for a Fibonacci proof [duplicate]

I have to prove $F^2_{n−1} = F^2_n + F^2_{n−1}$ for any $n >=1$ by induction (for the Fibonacci sequence). For the basis step, I have: $n = 1; $ $F_{(1)-1} = F^2_{(1)} + F^2_{(1)-1} ->$ $ ...
0
votes
2answers
77 views

Let $F_n$ denote the nth Fibonacci number and prove that the following re true for every possible integer $n$

$$\sum_{i = 1}^n F_{i}^2 = F_n F_{n+1}$$ -I solved a similar Fibonacci sequence that was the following: $$\sum_{i = 1}^n F_i = F_{n + 2} - 1$$ But, I am having trouble with this one, any help is ...
2
votes
0answers
27 views

Prove that $\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$ [duplicate]

I am asked: Let $F_{i}$ denote the $i$-th Fibonacci number. Prove that $$\sum^{n}_{i=0}\binom{n}{i}F_{i}=F_{2n}$$ I have the base case and the inductive hypothesis, but I'm not sure what ...
12
votes
1answer
346 views

How to prove this series about Fibonacci number: $\sum_{n=1}^{\infty }\frac{F_{n}}{2^{n}}=2$? [duplicate]

How to prove this series: I have no idea where to start. $$\sum_{n=1}^{\infty }\frac{F_{n}}{2^{n}}=2$$ where $F_{1}=1,~F_{2}=1,~F_n=F_{n-1}+F_{n-2},~~n\geq 3$.
3
votes
0answers
59 views

Fibonacci numbers properties

I've verified that $F_{41} \mod F_{32}= F_{23}$ where $41-32=9$ and $32-9=23$. I suppose these facts are correlated. Is there a simple way to show how? Simpler question: how can I justify that $...
1
vote
0answers
55 views

Help me find the mistake in my solution of the limit

Let $x_1=1, x_2=2,$ $$x_n=x_{n-1}+x_{n-2}, (n>2)$$ The task is to find: $$\lim \limits_{x\to\infty}\frac{x_{n+1}}{x_n}!$$ My attempt at solution: We write the recursive formula as: $$x_n-x_{n-1}-x_{...
4
votes
1answer
26 views

First Fibonacci Number with Given Remainder

I wonder is there more effective algorithm than brute-force-search to find the first Fibonacci number with given remainder $~~r~~$ modulo given integer $~~m~~$. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...