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
2answers
49 views

Restrictions for rule of general sequence: $T_{n+2}=T_{n} + T_{n+1}$

This is a rule which gives a sequence where $11$ times the seventh term ($11 t_7$) is equal to the sum of the first $10$ terms ($s_{10}$), where the first two starting numbers can be chosen. Do any ...
0
votes
1answer
38 views

Fibonacci numbers and proving using mathematical induction

I need to prove the rule below using Mathematical proof by induction but actually I'm stuck in the middle of the proving. $$F_n^2 - F_{n-1}F_{n+1} = (-1)^{n+1} {~\rm for~} n>1$$ If someone can ...
2
votes
1answer
69 views

Show that $\sum_{k=1}^{\infty}\frac{F_{2^{k-1}}}{L_{2^k}-2}=\frac{15-\sqrt{5}}{10}$

Show that$$\sum_{k=1}^{\infty}\frac{F_{2^{k-1}}}{L_{2^k}-2}=\frac{15-\sqrt{5}}{10},$$ where $F_n$ is a Fibonacci number and $L_n$ is a Lucas number.$^1$ Motivation: For example, when calculating ...
1
vote
0answers
43 views

Proofs with Fibonacci and Lucas numbers via induction

How would I go about proving the following sequence using induction on $k$? $2F_{2n+k} = F_{n+k}L_n + F_nL_{n+k}$ I know I have to show that it's true for $k = 1$, but I can't even seem to be able ...
0
votes
0answers
28 views

Fibonacci Sequence and Time taken

Consider the following (incomplete) java code, which calculates the Fibonacci numbers ...
5
votes
2answers
147 views

Deducing the closed form for pentagonal numbers

Consider the sequence: $0,1,5,12,22,35,51,70,92,117,145,176,\ldots$ Find both a recurrence and a closed form for this sequence. I've done some research and found out that the majority of ...
40
votes
5answers
992 views

Is ${F_{n}}^2 - 28$ always a composite number?

The problem is as follows: Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$ cannot be a prime. I came across this problem accidentally ...
0
votes
0answers
33 views

Pisano Period - Fibonacci

I have to construct an algorithm which will return a fibonacci number mod another integer. I know that i have to implement the Pisano period. I know how to receive it, but the problem comes when I ...
1
vote
3answers
40 views

Prove that the $c_{n}$ in $\frac{1}{1-z-z^{2}}=\displaystyle\sum_{n=0}^{\infty}c_{n}z^{z}$ satisfy a Fibonacci-like recurrence relation

I need to prove that the coefficients $c_{n}$ of the expansion $\frac{1}{1-z-z^{2}}\sum_{n=0}^{\infty}c_{n}z^{n}$ satisfy the recurrence relation $c_{0}=c_{1}=1$, $c_{n}=c_{n-1}+c_{n-2}$, by ...
10
votes
1answer
56 views

Alternative “Fibonacci” sequences and ratio convergence

So the well known Fibonacci sequence is $$ F=\{1,1,2,3,5,8,13,21,\ldots\} $$ where $f_1=f_2=1$ and $f_k=f_{k-1}+f_{k-2}$ for $k>2$. The ratio of $f_k:f_{k-1}$ approaches the Golden Ratio the ...
7
votes
1answer
1k views

Another way to go about proving the limit of Fibonacci's sequence quotient.

It is not difficult to inductively prove that $$\eqalign{ & \phi = \phi + 0 \cr & {\phi ^2} = \phi + 1 \cr & {\phi ^3} = 2\phi + 1 \cr & {\phi ^4} = 3\phi + 2 \...
9
votes
1answer
255 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$ ...
3
votes
1answer
83 views

Closed form for Fibonacci numbers

We know the closed form for Fibonacci number as $F_n=\frac{1}{\sqrt5}\left[\left(1+\frac{\sqrt5}{2}\right)^n−\left(1−\frac{\sqrt5}{2}\right)^n\right]$ But while finding $F_n \pmod{99991}$ the closed ...
3
votes
3answers
59 views

Recurrence Relation of a series

I know this would seem lame, but I need to ask this. I was trying to solve some recurrence based problems and I came across this series. $1,2,4,7,12,\dots$ Question was: To find the recurrence ...
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} ...
-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+...
3
votes
2answers
306 views

Magic Squares with Lucas and Fibonacci Numbers

I am quite curious about can we construct magic squares using only Lucas and Fibonacci numbers(of course not repeating them? If yes, how can we construct them? And if not , what is the proof?
7
votes
5answers
9k views

Prove this formula for the Fibonacci Sequence

This formula provides the $n$th term in the Fibonacci Sequence, and is defined using the recurrence formula: $u_n = u_{n − 1} + u_{n − 2}$, for $n > 1$, where $u_0 = 0$ and $u_1 = 1$. Show that ...
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$"...
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: ...
1
vote
3answers
134 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
4
votes
1answer
69 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
130 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?
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}...
12
votes
0answers
315 views

Are all totient values of Fibonacci Numbers distinct?

This question was inspired while I was seeing how certain recurrence relations would behave when I applied Multiplative Functions. Let $F_{n}$ be a sequence for which $F_{1}=1,F_{2}=1$, and $F_{n}=...
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\, .$$
2
votes
1answer
57 views

The sum of the Reciprocal of the Partial Sum of the Consecutive Fibonacci Numbers Series [closed]

How to prove that this conjecture is true for $n$th order Fibonacci number: $$1\le\sum_{n=1}^\infty\dfrac{1}{F_{n+2}-1}<2.5$$
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$$...
14
votes
4answers
5k views

Fibonacci modular results

Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which ...
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{ ...
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$ ...
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 ...
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})=(\...
1
vote
2answers
1k views

Formula for binary sequences of length m with no n consecutive 1s?

Formula for binary sequences of length $m$ with no $n$ consecutive $1$s? I know The number of binary strings of length $m$ without consecutive $1$s is the Fibonacci number $F_{m+2}$. But how about ...
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 ...
39
votes
13answers
6k views

How to prove that the Fibonacci sequence is periodic mod 5 without using induction?

The sequence $(F_{n})$ of Fibonacci numbers is defined by the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ for all $n \geq 2$ with $F_{0} := 0$ and $F_{1} :=1$. Without mathematical induction, ...
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 ...