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
    Are those binomial coefficients?2010-12-11
  • 0
    Yes.Yes.Yes.Yes.2010-12-11
  • 1
    If those are indeed binomial coefficients, the RHS for both ought to be $2^{n-2}$. In any event, the [binomial theorem](http://mathworld.wolfram.com/BinomialTheorem.html) is of use here.2010-12-11
  • 0
    Nopes in my module it's given that only the second is $n-2$.2010-12-11
  • 0
    Not gettin J.M could you please explain a bit more?2010-12-11
  • 1
    Let's take the case $n=3$ as an example. The first summation claims that $C(1,-1)+C(1,0)+C(1,1) = 2^2$. Conventionally $C(1,-1)$ is zero, so the claim is incorrect. Similarly the second summation claims $C(1,0)+C(1,1)+C(1,2) = 2^2$, and since $C(1,2)$ is zero by convention, is similarly incorrect. Perhaps something was omitted in the text?2010-12-11
  • 0
    $$\sum_{r=1}^n \binom{n-2}{r-2}=\sum_{r=2}^n \binom{n-2}{r-2}=\sum_{r+2=2}^{r+2=n} \binom{n-2}{r+2-2}=\sum_{r=0}^{n-2} \binom{n-2}{r}$$2010-12-11
  • 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
    The LHS is same as I mentioned that's creating some confusion in my mind.2010-12-11
  • 0
    @Debanjan: No, I meant what the LHS should equal as a power of $2$.2010-12-11
  • 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}$.