Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I found three difficult problems for me, involving binomial coefficients. They are extremely interesting I think, but I don't know if I have enough knowledge to manage. Seem really hard, can you help me with them?

  1. Prove that every $z\in\mathbb{N}$ we can represent (in one and only one way) by $$ z={x+y+1\choose 2}+x $$ for some $x,y\in\mathbb{N}$.

  2. Show that the number: $$ \sum_{k\ge 0}{n\choose k}F_{m+k} $$ is some Fibonacci number for $m,n\in\mathbb{N}$

  3. How many sequences consisting of $0$ and $1$ are there, where we have $2n$ zeros and $2n$ ones, but before $n$-th $1$ in sequence we have at most $n$ zeros?

share|cite|improve this question
What did you try? – Did Jul 30 '12 at 12:14
For the first one consider $k_0 := \min \left\{ k, \ \frac{1}{2}k(k+1) < z \right\}$ – vanna Jul 30 '12 at 12:16
up vote 1 down vote accepted

Hints :

  1. Make a table, where you put $x$ in the column, and $y$ in the row, and the corresponding $z$ in each cell. That should be enough to give you an idea of the proof
  2. The proof is simple for $n=1$. Now, from a formula for $n$, show you can obtain any formula for $n+1$ by decomposing $F_{n+2}=F_{n+1}+F_n$
  3. Find a recursive formula that counts your sequences... (The solution is catalan numbers, those words are the dyck words)
share|cite|improve this answer
2.For $n=1$: $\sum_{k\ge 0}{1\choose k}F_{m+k}=F_m+F_{m+1}$, which is a Fibonacci number for every $m\in\mathbb{N}$. Let us consider $n+1,m'\in\mathbb{N}$, then we have: $\sum_{k\ge 0}{n+1\choose k}F_{m'+k}=\sum_{k\ge 0}{n\choose k}F_{m'+k}+\sum_{k\ge 0}{n\choose k}F_{m'+k+1}=\sum_{k\ge 0}{n\choose k}F_{m'+k+2}$, so setting $m'=m-2$ and by induction we can get any Fibonacci number that we want. Is that correct? Unfortunately I still don't know how to approach the other two problems. In 3 I think that recursion should consist of two recursions - end with $1$ and end with $0$. In 1 no idea. – ray Jul 30 '12 at 16:31
I'm afraid something can be wrong with my reasoning for 2. $m$ is supposed to be a natural number, but I am setting $m'=m-2$ for every next $n$ so I can get negative value of $m$ after some time. On the other hand there can be any $m$ for a given $n$. So is there anything I should worry about this proof? – ray Jul 30 '12 at 16:46
I don't think the solution for 3. are catalan numbers. for $n=1$ we have sequences: $0101, 0110, 1100, 1010, 1001$, and that all we have and $5$ isn't the catalan number. – ray Jul 30 '12 at 19:16
this is because you have 2n, you will obtain $C_{2n+1}$. The $+1$ come from the at most $n$ zeros instead of $n-1$. – Xoff Jul 30 '12 at 20:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.