2
$\begingroup$

These two appear in my module (without any proof):

$\sum_{r = 1}^{n} C(n-2,r-2) = 2^{n-1}$

$\sum_{r = 0}^{n-1} C(n-2,r) = 2^{n-2}$

For the first one when when $r=1 \Rightarrow C(n-2,1-2) = C(n-2,-1)$ ?!The same thing for $r=n-1$ in the second one,are they valid if yes,please explain how?

  • 0
    @hardmath:Thanks I was missing that part only.2010-12-11

2 Answers 2

5

Hint: Use the binomial expansion for $(1+x)^{n-2}$ and choose an appropriate value for $x$. Binomial coefficients with a negative value of $r$ are zero. You should see what the LHS ought to be.

  • 0
    Got it thanks Timothy!2010-12-11
3

In addition to the calculation implied by Timothy's answer, let me describe a way to see it directly. Consider $\sum_{r=0}^{n-1}C(n-2,r)$. This is the sum of

(the number of ways of choosing a subset of $0$ elements out of a set of $n-2$ elements)

+ (the number of ways of choosing a subset of $1$ element out of a set of $n-2$ elements)

+ (the number of ways of choosing a subset of $2$ elements out of a set of $n-2$ elements)

. . . + (the number of ways of choosing a subset of $n-1$ elements out of a set of $n-2$ elements)

Since any subset of $n-2$ elements has either 0, 1, 2, . . . , or $n-2$ elements, the total is just the number of ways of choosing any subset of $n-2$ elements. And this is just $2^{n-2}$.