Prove Binomial Identity: Differentiation vs Subsitution

[chaotixmonjuish]

Prove this using this identity:
<br /> k\binom{n}{k}=n\binom{n-1}{k-1}<br />
<br /> \binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}+...+(-1)^n-1\binom{n}{n}<br />

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:
<br /> k\binom{n}{k}=n\binom{n-1}{k-1}<br />
<br /> \binom{n}{1}-2\binom{n}{2}+3\binom{n}{3}+...+(-1)^n-1\binom{n}{n}<br />

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:

<br /> \binom{n}{1}-2\binom{n}{2}+...+(-1)^k\binom{n}{n}<br />
Using the binomial theorem
<br /> \sum_{k=0}^{n}\binom{n}{k}x^{k}=(1+x)^{n}<br />
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
<br /> \sum_{k=0}^{n}k\binom{n}{k}x^{k-1}=k(1+x)^{n}<br />
so that
<br /> \sum_{k=1}^{n-1}n\binom{n-1}{k-1}=k(x)^{k-1}<br />
<br /> \sum_{l=0}^{n}n\binom{n-1}{l}x^{k-1}<br />

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

 

[tiny-tim]

Why are you making this so complicated?

Start with <br /> \sum_{l=0}^{n-1}n\binom{n-1}{l}<br /> …

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

<br /> \sum_{l=0}^{n-1}\binom{n-1}{l}<br /> ?

 

[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}<br /> (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

<br /> n\sum_{k=1}^{n-1} \binom{n-1}{l}x^{l-1}<br />

 

[tiny-tim]

so would the final answer be

<br /> n\sum_{k=1}^{n-1} \binom{n-1}{l}x^{l-1}<br />

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?

)