The bijective thing has kinda thrown me off but here's how it's proved...

(Although I suppose equality is a bijection so... I dunno)

Use induction.

Base case.

holds as both equal 1 so we have our inductive case.

Assume that it is true for (>k), i.e, assume that.

Now prove for the case n+1, i.e. show that...

Now we have,

Now just expand using and it should come out to be . Hence the relationship holds for all .

(If you get stuck on the last part, look up Pascal's Rule).