3
$\begingroup$

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?

  • 0
    For the first one consider k_0 := \min \left\{ k, \ \frac{1}{2}k(k+1) < z \right\}2012-07-30

1 Answers 1

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)
  • 0
    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$.2012-07-30