3

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?

Vincenzo Tibullo
  • 10,955
ray
  • 1,507

1 Answers1

1

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)
Xoff
  • 10,310
  • 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