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?

$\endgroup$
  • $\begingroup$ Are those binomial coefficients? $\endgroup$ – J. M. is a poor mathematician Dec 11 '10 at 15:12
  • $\begingroup$ Yes.Yes.Yes.Yes. $\endgroup$ – Quixotic Dec 11 '10 at 15:14
  • 1
    $\begingroup$ 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. $\endgroup$ – J. M. is a poor mathematician Dec 11 '10 at 15:15
  • $\begingroup$ Nopes in my module it's given that only the second is $n-2$. $\endgroup$ – Quixotic Dec 11 '10 at 15:16
  • 1
    $\begingroup$ 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? $\endgroup$ – hardmath Dec 11 '10 at 15:26
5
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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