8
votes
3answers
108 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
87 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
47 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
123 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
177 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
351 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
54 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
163 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
218 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
128 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
386 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}$: ...
10
votes
4answers
3k views

The generating function for the Fibonacci numbers

$$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\}$. Please HELP. Thanks guys.
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
168 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
155 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
577 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
220 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
391 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
58 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
149 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
184 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
362 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
80 views

Existence of 5-d centrally symmetric self-dual polytope

Does there exist a 5-dimensional centrally symmetric self-dual polytope?
1
vote
2answers
107 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
222 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
231 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 ...
4
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
167 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
95 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
333 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
2k 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} ...
16
votes
15answers
5k views

Applications of the Fibonacci sequence

The Fibonacci sequence is very well known, and is often explained with a story about how many rabbits there are after $n$ generations if they each produce a new pair every generation. Is there any ...
20
votes
7answers
880 views

How are we able to calculate specific numbers in the Fibonacci Sequence?

I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...