Can the summation formula be proven by counting a set in two ways?

[Robb]

Mod note: Fixed numerous problems with LaTeX
Also, the fractions shown throughout should instead be binomial coefficients
1. Homework Statement
prove the summation formula by counting a set in two ways

$$\sum_{k=0}^n k\left( \frac n k \right) = n *2^{n-1}$$

Homework Equations

LHS = $k \left(\frac n k \right) = k \left (\frac n 0 \right) + k \left( \frac n 1 \right) + k \left( \frac n 2 \right) + ...+ k \left(\frac n n \right) = k * 2^{n}$

RHS = $n \left (\frac n k \right) * 2^{-1}$

The Attempt at a Solution

Part two is just some analysis on my part. I'm not sure how to choose a set to count. A hint from the back of the book says to split the RHS into subsets corresponding to the term on the left. First attempt at latex so hope its not too confusing.

 

[Orodruin]

Please make sure your LaTeX is correct by using the preview button.

 

[Robb]

Please make sure your LaTeX is correct by using the preview button.

Is there a way to see how the actual equations will show once posted? The preview just shows the LateX string.

 

[Mark44]

First attempt at latex so hope its not too confusing.

I've fixed it, but there were many errors.

Is there a way to see how the actual equations will show once posted? The preview just shows the LateX string.

This means that your LaTeX is not well-formed. If it's not right, keep revising it until it shows up as you intend in the Preview.

Here are some of the things that were wrong:
LaTeX expressions need to start and end with either ## pairs (inline LaTeX) or $$ pairs (standalone)
frac needs to be preceded by \, as in \frac. Most or all of yours were missing the slash.
The left and right commands can't have spaces between \ and left or right, and there can't be a space between left or right and the enclosing symbol. IOW, do this \left(, not this: \ left (.

There's a link to our tutorial at the lower left corner of the input pane.

 

[Robb]

I've fixed it, but there were many errors.
This means that your LaTeX is not well-formed. If it's not right, keep revising it until it shows up as you intend in the Preview.

Here are some of the things that were wrong:
LaTeX expressions need to start and end with either ## pairs (inline LaTeX) or $$ pairs (standalone)
frac needs to be preceded by \, as in \frac. Most or all of yours were missing the slash.
The left and right commands can't have spaces between \ and left or right, and there can't be a space between left or right and the enclosing symbol. IOW, do this \left(, not this: \ left (.

There's a link to our tutorial at the lower left corner of the input pane.

Much obliged!

 

[Mark44]

Also, the equation you're working with is wrong, I believe, and you mistakenly have fractions throughout your work.

$$\sum_{k=0}^n k\left( \frac n k \right) = n *2^{n-1}$$

In the summation, you should have binomial coefficients, not fractions.
$\binom n k$, not $\frac n k$

The command I used is \binom

 

[Robb]

Also, the equation you're working with is wrong, I believe, and you mistakenly have fractions throughout your work.

In the summation, you should have binomial coefficients, not fractions.
$\binom n k$, not $\frac n k$

The command I used is \binom

OK. That was my intent (obviously). Is there a way to preview so that I can see what the output would look like once it posts? Then I will know I messed up before I send it to the whole world.

 

[Mark44]

OK. That was my intent (obviously). Is there a way to preview so that I can see what the output would look like once it posts? Then I will know I messed up before I send it to the whole world.

Yes, use the PREVIEW button.

 

[Robb]

Yes, use the PREVIEW button.

It only shows me the LateX not how it would appear once posted.

 

[Mark44]

It only shows me the LateX not how it would appear once posted.

Scroll up or down (I don't remember which) to see how it actually renders.

 

[Ray Vickson]

OK. That was my intent (obviously). Is there a way to preview so that I can see what the output would look like once it posts? Then I will know I messed up before I send it to the whole world.

Instead of "\binom" you can also get ${n \choose m}$ by typing {n \choose m}.

 

[Orodruin]

Is there a way to see how the actual equations will show once posted? The preview just shows the LateX string.

If you do it correctly it shows up. If it does not there are errors in parsing your equations.

 

[StoneTemplePython]

The Attempt at a Solution

Part two is just some analysis on my part. I'm not sure how to choose a set to count. A hint from the back of the book says to split the RHS into subsets corresponding to the term on the left.

Did you make any progress on this? As a hint, I'd suggest considering $(1+1)^{n-1}$.

 

[Robb]

Did you make any progress on this? As a hint, I'd suggest considering $(1+1)^{n-1}$.

I guess I'm not sure what this does for me.

 

[StoneTemplePython]

I guess I'm not sure what this does for me.

ok, I'll nudge you a bit more:
consider $(1+1)^{n-1}$ and calculate it two different ways... one, directly $=(2)^{n-1}$, which seems a lot like your right hand side. Apply the binomial formula for the other way of calculating... what does that look like?

 

[Robb]

ok, I'll nudge you a bit more:
consider $(1+1)^{n-1}$ and calculate it two different ways... one, directly $=(2)^{n-1}$, which seems a lot like your right hand side. Apply the binomial formula for the other way of calculating... what does that look like?

Ok, I think I get it. When they ask to count two different ways, I assume I am suppose to count one way on side and another way on the other and if I get the same result then they are equivalent?

 

[StoneTemplePython]

Ok, I think I get it. When they ask to count two different ways, I assume I am suppose to count one way on side and another way on the other and if I get the same result then they are equivalent?

Basically -- it kind of depends on how you think about it. In this case I think it's a little stronger:

You know that $(1+1)^{n-1} = (1+1)^{n-1}$
and you compute / expand / show it 2 different legal ways (for this problem: one is by making use of parenthesis and addition, the other is the binomial formula) but you know those two different forms are equivalent precisely because $(1+1)^{n-1} = (1+1)^{n-1}$

 

[Robb]

Basically -- it kind of depends on how you think about it. In this case I think it's a little stronger:

You know that $(1+1)^{n-1} = (1+1)^{n-1}$
and you compute / expand / show it 2 different legal ways (for this problem: one is by making use of parenthesis and addition, the other is the binomial formula) but you know those two different forms are equivalent precisely because $(1+1)^{n-1} = (1+1)^{n-1}$

Awesome! Thanks so much!