# Problem with induction of binomial coefficiency

(Sorry for making up math language, I am roughly translating math terms here)

This is part of some of the induction exercises in the book "Otto Forster: Analysis 1" (1.2):

$$\binom{x+y}{n}=\sum_{k=0}^{n}\binom{x}{n-k}\binom{y}{k}.$$

$$(a_n = b_n)$$

I am also instructed to consider that: $$\binom{x}{k}=\prod_{j=1}^{n}\frac{x-j+1}{j}$$

I think I understood what induction is, and I am also able to make simple induction proofs, but this one is kind of hard to me. Normally I try to extract a statement from one side of the equation the resembles the "step forward" in the term/sequence. As in $a_{n+1} - a_n = a_{dif}$, and then try to add that "difference" to the other side of the equation to see if I can form something like $b_n + a_{dif} = b_{n+1}$. However this simplefied technique doesn't seem to work on this excersice. Nothing I do seems to lead anywhere, mostly because of $\sum_{k=0}^{n}\binom{x}{n-k}\binom{y}{k}$ (Normally I can just "take off" the last member (n+1) of the sum and hook it onto the other term)

Is this really as hard as I feel it is? Is my approach just unsuited for this problem? I could really use some clues on how to move on here.

• $C_{n-k}=C_{n}$ then use your instruction – Archis Welankar Jan 10 '16 at 10:24
• As in $a_{n-k} = b_n$ ? I am unfamiliar with the meaning of C. – John Smith Jan 10 '16 at 10:47
• Its $nCr ={n\choose r}$ – Archis Welankar Jan 10 '16 at 10:50