Prove Binomial Identity: Differentiation vs Subsitution

[chaotixmonjuish]

Prove this using this identity:
$$k\binom{n}{k}=n\binom{n-1}{k-1}$$
[tex]
\binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}+...+(-1)^n-1\binom{n}{n}
[/tex]

I was able to do this via differentiation, but not using this substitution. Any hints would be great.

 

[tiny-tim]

Hi chaotixmonjuish!

(use ^ and _ not sup and sub in latex )

Prove this using this identity:
$$k\binom{n}{k}=n\binom{n-1}{k-1}$$
[tex]
\binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}+...+(-1)^n-1\binom{n}{n}
[/tex]

I was able to do this via differentiation, but not using this substitution. Any hints would be great.

Well, the n is the same all the way through, that leaves a sum which should be easy.

 

[chaotixmonjuish]

what do you mean?

 

[tiny-tim]

what do you mean?

Show us what you get when you substitute.

 

[chaotixmonjuish]

Well this is something I sort of worked out:

$$\binom{n}{1}-2\binom{n}{2}+...+(-1)^k\binom{n}{n}$$
Using the binomial theorem
$$\sum_{k=0}^{n}\binom{n}{k}x^{k}=(1+x)^{n}$$
Are you saying I can just throw in the identity without doing anything or would I have to multiply across with a k so that
$$\sum_{k=0}^{n}k\binom{n}{k}x^{k-1}=k(1+x)^{n}$$
so that
$$\sum_{k=1}^{n-1}n\binom{n-1}{k-1}=k(x)^{k-1}$$
$$\sum_{l=0}^{n}n\binom{n-1}{l}x^{k-1}$$

I'm ignoring 1 because 1 to any power is 1

 

[tiny-tim]

Why are you making this so complicated?

Start with $$\sum_{l=0}^{n-1}n\binom{n-1}{l}$$ …

what (in ordinary language) is (i'm leaving out the n ) …

$$\sum_{l=0}^{n-1}\binom{n-1}{l}$$ ?

 

[chaotixmonjuish]

Well k-1=n, if that is what you are hinting at.

 

[tiny-tim]

No … what (in ordinary language) is $$\binom{n-1}{l}$$ (or ^n-1C_l) …

it's the number of … ?

 

[chaotixmonjuish]

Its sort of like saying its the number of ways you can select a leader (n), then how many different ways you can't form a team for leader $$\binom{n-1}{l}$$

 

[tiny-tim]

Its sort of like saying its the number of ways you can select a leader (n), then how many different ways you can't form a team for leader $$\binom{n-1}{l}$$

Yes …

^n-1C_l is the number of ways of choosing l things from n-1 …

so (to get the ∑) what is the number of ways of choosing 1 thing or 2 things or … n-1 things from n-1?

 

[chaotixmonjuish]

so would the final answer be

$$n\sum_{k=1}^{n-1} \binom{n-1}{l}x^{l-1}$$

 

[tiny-tim]

so would the final answer be

$$n\sum_{k=1}^{n-1} \binom{n-1}{l}x^{l-1}$$

i said you were making this complicated …

wherever did x come from?

(and you never answered:

what is the number of ways of choosing 1 thing or 2 things or … n-1 things from n-1?

)