Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Are those binomial coefficients? –  J. M. Dec 11 '10 at 15:12
    
Yes.Yes.Yes.Yes. –  Quixotic Dec 11 '10 at 15:14
1  
If those are indeed binomial coefficients, the RHS for both ought to be $2^{n-2}$. In any event, the binomial theorem is of use here. –  J. M. Dec 11 '10 at 15:15
    
Nopes in my module it's given that only the second is $n-2$. –  Quixotic Dec 11 '10 at 15:16
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? –  hardmath Dec 11 '10 at 15:26

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
The LHS is same as I mentioned that's creating some confusion in my mind. –  Quixotic Dec 11 '10 at 15:21
    
@Debanjan: No, I meant what the LHS should equal as a power of $2$. –  Timothy Wagner Dec 11 '10 at 15:22
    
Got it thanks Timothy! –  Quixotic Dec 11 '10 at 15:31

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.