1
vote
2answers
67 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 ...
-6
votes
0answers
107 views

Solve fibonacci equation

Given two numbers M and N we need to solve : ( ∑ ( 6 * x * y * z * Fibo[x] * Fibo[y] * Fibo[z] ) ) % M , where x + y + z = N. Here x, y, z ≥ 0 and are integers. ...
8
votes
3answers
113 views

Asking About Binomial Sum Related to Fibonacci

How would I prove $$ \sum\limits_{i,j\ge 0} {n-i \choose j} {n-j \choose i}=F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of Fibonacci numbers? Thank you very ...
5
votes
1answer
90 views

Number of zeros in Fibonacci sequences mod $p$

We know that Fibonacci sequences are periodic in mod $m$. For example, for $p\equiv \pm 1 \pmod 5$ and $\pm 2 \pmod 5$ the periods for Fibonacci sequences modulo $p$ divide $p-1$ and $2p+2$ ...
1
vote
1answer
52 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
1
vote
1answer
126 views

Calculate Number of ways to make the grid

We wish to tile a grid of size Nx2 with rectangles (dominoes) of 2x1 (in either orientation).For given N I need to find the number of different ways to tile the grid. EXAMPLE : For N=1 answer is 1 ...
5
votes
2answers
178 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
1
vote
1answer
423 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 ...
3
votes
1answer
62 views

All pairs sum to a different value

If we consider the integers $\{1,\dots,n\}$, what is the size of the largest subset $A$ so that all distinct pairs $x, y \in A$ sum to a different value? For this to make sense $(x,y)$ and $(y,x)$ ...
2
votes
2answers
55 views

Why is $\sum_{k=0}^{n} f(n,k) = F_{n+2}$?

If $f(n,k)$ is the number of $k$ size subsets of $[ n ] = { 1 , \ldots , n }$ which do not contain a pair of consecutive numbers, how can I show that $\sum_{k=0}^{n} f(n,k) = F_{n+2}$? ($F_{n}$ is the ...
2
votes
2answers
78 views

Fibonacci combinatorial identity

Can someone explain how to prove the following identity involving Fibonacci sequence $F_n$ $F_{2n} = {n \choose 0} F_0 + {n\choose 1} F_1 + ... {n\choose n} F_n$ ?
1
vote
5answers
170 views

A Non-recursive Fibonacci Sequence

How can I determine the general term of a Fibonacci Sequence? Is it possible for any one to calculate F2013 and large numbers like this? Is there a general formula for the nth term of the Fibonacci ...
0
votes
2answers
83 views

Prove the following identity for Fibonacci numbers

Prove this: for any positive integer $a,b,c$, $F_{a+b+c+3}=F_{a+2}(F_{b+2}F_{c+1}+F_{b+1}F_c)+F_{a+1}(F_{b+1}F_{c+1}+F_bF_c)$ Is there any way other than induction to prove this?
3
votes
2answers
149 views

Finite bit strings that do not contain '$00$'

I am studying for an exam and I am having trouble with this practice question: In this question, we consider finite bit strings that do not contain $00$. Examples of such bitstrings are $0101010101$ ...
1
vote
1answer
31 views

Determine the number of n-term sequences of 0s and 1s containing no two consecutive $0$s

I am reading a chapter about Fibonacci number and generating function. And there's a question come up but without solution. I think about it for quite some time, but still can't come up with a ...
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
66 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} $$ ...
2
votes
1answer
227 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
1answer
130 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
121 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
2answers
393 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}$: ...
11
votes
4answers
4k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers $\left\{1,1,3,5,8,13,21,...\right\}$.
1
vote
2answers
142 views

Combinatorics — Fibonacci

For the following expression, find a simple formula which only involves one Fibonacci number. Then prove it by induction. $$F_1+F_3+ \cdots +F_{2n+1} $$ I'm be appreciated for any help. I have no ...
2
votes
1answer
174 views

Number of Permutations Fixed by the Fundamental Transformation is Fibonacci

Writing a permutation in $S_n$ as a product of disjoint cycles, we define a standard representation by writing each cycle with its largest element first, and ordering the cycles by the increasing ...
0
votes
2answers
214 views

Verify the following identity for Fibonacci numbers

This is a homework problem that I would very much appreciate some help with. Thanks!
5
votes
3answers
159 views

Summation of Fibonacci numbers.

Let $f_n$ be the sequence of Fibonacci numbers. We need to show that $$\sum_{n\ge0} f_n x^n = \dfrac{1}{1-x-x^2}$$ I remember a solution when we are using the generating functions like: $f(x) = F_0 ...
1
vote
4answers
159 views

Fibonacci sequence

Given an integer $n ≥ 1$, let $f_n$ be the number of lists whose elements all equal $1$ or $2$ and add up to $n−1$. For example $f_1 = 1 = f_2$ because only the empty list ($0$ ones and $0$ twos) sums ...
1
vote
0answers
63 views

combinatorial proof of Fibonacci identities [duplicate]

Give a combinatorial proof to each of the Fibonacci identities: $$nF_0+(n-1)F_1+\dots\dots+2F_{n-2}+F_{n-1}=F_{n+3}-(n+2)$$ and $$ F_2+F_5+\dots\dots+F_{3n+1}=\frac{F_{3n+1}-1}{2} $$ Assume that ...
7
votes
7answers
585 views

Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality: $$ \sum\limits_{k=0}^n {n-k \choose k} = F_{n} $$ where $F_{n}$ is a n-th Fibonacci number. The problem seems easy but I can't find the way to ...
3
votes
5answers
223 views

Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?)

Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method? I'm trying to exclude external libraries like cmath or ...
7
votes
2answers
393 views

Fibonacci numbers divisible by $9$

The $n$th Fibonacci number $F_n$ is defined as follows,$$F_1=F_2=1\mbox{ and } F_{n+2}=F_{n+1}+F_{n}\mbox{ for } n\geq 1$$ I want to know how many of the first $1000$ Fibonacci numbers are divisible ...
2
votes
2answers
59 views

Non-isomorphic combinatorial classes with growth rate equal to the golden ratio?

In a couple of weeks, I'm giving a talk about the growth rates of some combinatorial classes. In the introduction, I thought I'd present the class of tilings of a $n\!\times\!2$ strip with dominos, ...
2
votes
1answer
150 views

Another Bijective proof for Fibonacci Identities

I'm going through a past exam, and this question popped up: Prove: $3P_n = P_{n-2} + P_{n+2},\,n>2$ Where $\tilde{P}_j = \{\textrm{monomer-dimer pavings on a } 1\times j \textrm{ board}\}$ and ...
2
votes
1answer
187 views

Bijective Proof of a Fibonacci Identity

Prove (Using bijections): $F_{1}+F_{3}+\cdots+F_{2n-1}=F_{2n}$ Where $F_{i}$ is the $i$th Fibonacci number. Apparently you use monomers and dimers to prove this, but I don't really know what to ...
4
votes
2answers
112 views

How many ways to reach $1$ from $n$ by doing $/13$ or $-7$?

How many ways to reach $1$ from $n$ by doing $/13$ or $-7$ ? (i.e., where $n$ is the starting value (positive integer) and $/13$ means division by $13$ and $-7$ means subtracting 7)? Let the number ...
2
votes
1answer
364 views

Proof about lucas numbers.

Define the lucas numbers to be $$l_n = l_{n-1} + l_{n-2} $$ if $n \ge 2$ with initial conditions $l_0 = 2$ and $l_1= 1$ I "proved" by induction that $l_n = f_{n-1} + f_{n+1}$ for $n \ge 1$ (by ...
1
vote
2answers
84 views

Existence of 5-d centrally symmetric self-dual polytope

Does there exist a 5-dimensional centrally symmetric self-dual polytope?
1
vote
2answers
109 views

Proof for one of the Lucas problem

Can anybody provide a combinatorial proof or algebraic proof of following identity? $${n\choose 0 }+ {n-1\choose 1}+{n-2\choose 2}+ .. +{{n-\lfloor n/2\rfloor} \choose {\lfloor n/2\rfloor}} = ...
4
votes
1answer
227 views

Generating Function of Even Fibonacci

I was posed the following question recently on an exam: Determine the generating function of the even-indexed Fibonacci numbers $F_{2n}$ given that the generating function of Fibonacci numbers is ...
0
votes
1answer
234 views

Fibonacci sequence, strings without 00, and binomial coefficient sums

Refer to the sequence $S$ where $S_n$ denotes the number of n-bit strings that do not contain the pattern 00. By considering the number of n-bit strings with exactly i 0's, show that $\displaystyle ...
5
votes
4answers
2k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...
2
votes
1answer
172 views

An identity involving Lucas numbers

Let $L_n$ be the Lucas numbers, defined by $L_n = F_{n-1} + F_{n+1}$ where f is the Fibonacci numbers. How to prove that $L_{2n+1} = \displaystyle \sum_{k=0}^{\lfloor n + 1/2\rfloor}\frac{2n+1}{2n+1 ...
2
votes
1answer
96 views

How to calculate variety of a vector under this constraint?

I am currently working through W. Ross Ashby's An Introduction to Cybernetics, and I'm stuck on a problem of calculating variety for a vector. I know the answer (I caved and checked), but I can't ...
7
votes
3answers
2k views

Fibonacci sequence divisible by 7?

Make and prove a conjecture about when the Fibonacci sequence, $F_n$, is divisible by $7$. I've realized it's when $n$ is a multiple of $8$. I just don't know how to go about proving it.
1
vote
3answers
270 views

Fibonacci Numbers: Is This Notation Clear? How Can It Be Improved?

I am writing up an assignment with includes many identities of Fibonacci numbers. I have made up the following notation (here $f_n$ is the number of tilings of an $n$-board by dominoes and squares - a ...
1
vote
1answer
337 views

Lucas Numbers and Tilings

Show that $f_{n-1} + L_n = 2f_{n}$. So we need to find a $2$ to $1$ correspondence. Set 1: Tilings an $n$-board. Set 2: Tiling of an $n-1$-board or tiling of an $n$-bracelet. So we need to ...
14
votes
1answer
1k views

Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number? $$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$ It's not in the place I thought it ...
2
votes
1answer
347 views

What is the least upper bound on the number of pairs of disjoint subsets of a binary step-order set S whose sums differ by 1?

Define a binary step-order set as a finite set S of positive integers si, i = 0 to n-1, where si ≡ 2i (mod 2i+1) for each i from 0 to n-1. So, i is the power of 2 appearing in the prime factorization ...
47
votes
1answer
3k views

Quadratic reciprocity via generalized Fibonacci numbers?

This is a pet idea of mine which I thought I'd share. Fix a prime $q$ congruent to $1 \bmod 4$ and define a sequence $F_n$ by $F_0 = 0, F_1 = 1$, and $\displaystyle F_{n+2} = F_{n+1} + \frac{q-1}{4} ...