# Three problems with binomial coefficients

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?

-
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

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$
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