Value of summation involving combination

[songoku]

Homework Statement

Find

$$\sum_{k=1}^{64} {64 \choose k} 64k$$

Homework Equations

Not sure

The Attempt at a Solution

Please give me hint how to start doing this question

 

[PeroK]

Homework Statement

Find

$$\sum_{k=1}^{64} {64 \choose k} 64k$$

Homework Equations

Not sure

The Attempt at a Solution

Please give me hint how to start doing this question

Work it out for n = 1, 2, 3, 4, 5 and see whether you can spot a pattern. Then, perhaps, try induction on $n$ to prove a general formula. Finally, set $n = 64$

 

[haruspex]

A standard method for getting rid of an awkward factor consisting of the index variable (the k in 64k) is to make the sum a function of some unknown, s say, by multiplying the k^th term by s to some power. E.g.
$$\sum_{k=1}^{64} {64 \choose k} 64k s^k$$
What would happen if you tried to integrate that wrt s? Ok, so try a slightly different power.

 

[Ray Vickson]

Homework Statement

Find

$$\sum_{k=1}^{64} {64 \choose k} 64k$$

Homework Equations

Not sure

The Attempt at a Solution

Please give me hint how to start doing this question

Here is a little hint for a non-calculus solution, using n = 4 instead of n = 64. Note that for $k =0$ we have $0 {4 \choose 0} = 0$, so we can start the summation from $k = 0$ instead of $k = 1$. Let $S_4 = \sum_{k=0}^4 k {4 \choose k}$. We have
$$S_4 = 0 {4 \choose 0} + 1 {4 \choose 1} + 2 {4 \choose 2} + 3 {4 \choose 3} + 4 {4 \choose 4}$$.
However, we have ${n \choose k} = {n \choose n-k}$ for all $k$, so we can write
$$S_4 = 0 {4 \choose 4} + 1 {4 \choose 3} + 2 {4 \choose 2} + 3 {4 \choose 1} + 4 {4 \choose 0} $$.
Now add the two forms together, collecting coefficients of each ${4 \choose j}$. That will give you
$$2S_4 = (0+4) {4 \choose 0} + (1+3) {4 \choose 1} + \cdots + (4 + 0) {4 \choose 4} = 4 \sum_{k=0}^4 {4 \choose k}.$$
Do you recognize that last summation?

 

[songoku]

Work it out for n = 1, 2, 3, 4, 5 and see whether you can spot a pattern. Then, perhaps, try induction on $n$ to prove a general formula. Finally, set $n = 64$

Maybe the pattern you are referring is the same as Ray Vickson?

Here is a little hint for a non-calculus solution, using n = 4 instead of n = 64. Note that for $k =0$ we have $0 {4 \choose 0} = 0$, so we can start the summation from $k = 0$ instead of $k = 1$. Let $S_4 = \sum_{k=0}^4 k {4 \choose k}$. We have
$$S_4 = 0 {4 \choose 0} + 1 {4 \choose 1} + 2 {4 \choose 2} + 3 {4 \choose 3} + 4 {4 \choose 4}$$.
However, we have ${n \choose k} = {n \choose n-k}$ for all $k$, so we can write
$$S_4 = 0 {4 \choose 4} + 1 {4 \choose 3} + 2 {4 \choose 2} + 3 {4 \choose 1} + 4 {4 \choose 0} $$.
Now add the two forms together, collecting coefficients of each ${4 \choose j}$. That will give you
$$2S_4 = (0+4) {4 \choose 0} + (1+3) {4 \choose 1} + \cdots + (4 + 0) {4 \choose 4} = 4 \sum_{k=0}^4 {4 \choose k}.$$
Do you recognize that last summation?

I get your hint. Thanks

A standard method for getting rid of an awkward factor consisting of the index variable (the k in 64k) is to make the sum a function of some unknown, s say, by multiplying the k^th term by s to some power. E.g.
$$\sum_{k=1}^{64} {64 \choose k} 64k s^k$$
What would happen if you tried to integrate that wrt s? Ok, so try a slightly different power.

I am not sure I get your hint but I am interested to know how to solve the question using integration.

I try to use s^k-1 and after integration with respect to s, I get ₆₄C_k . 64 . s^k
I am guessing I need to use upper and lower limit for the integration (and maybe it is 1 and 0). But I think I am missing something that relates the summation and the integration.

Maybe I need to find a form similar to:

$$\sum_{k=1}^{64} {64 \choose k} 64k = \int_{a}^{b} {64 \choose k} 64k s^{k-1} ds $$

but I am not sure how

 

[haruspex]

I try to use sk-1 and after integration with respect to s, I get ⁶⁴C_k . 64 . s^k

Yes, that's the right step.
Do you not recognise that sum? (Binomial Theorem.)

 

[songoku]

Yes, that's the right step.
Do you not recognise that sum? (Binomial Theorem.)

I recognise that sum, sum of coefficient of pascal triangle which will lead to 2ⁿ

What I am confused about is how to write down the systematic mathematical step and how it leads to a proper presentation of answer.

I start by denoting ⁶⁴C_k . 64k as U_k.

U_k = ⁶⁴C_k . 64k

Then multiplying the term with s^k-1, it becomes:

U_k = ⁶⁴C_k . 64k . s^k-1

Then integrating both sides, I get:

$$\int_{0}^{1} U_{k} ~ ds = \int_{0}^{1} {64 \choose k} 64k s^{k-1} ds $$

$$\int_{0}^{1} U_{k} ~ ds = {64 \choose k} 64$$

Then, how I relate the result of integration to the sum that the question asked? I mean, my result does not have sigma sign on the RHS so how can I make it becomes like:

$$ {64 \choose k} 64 = \sum_{k=0}^{k=64} {64 \choose k} 64 $$

 

[haruspex]

integrating both sides, I get:

Keep it as an indefinite integral. You will need to differentiate wrt s later.

 

[songoku]

Keep it as an indefinite integral. You will need to differentiate wrt s later.

So:
$$\int U_{k} ~ ds = \int {64 \choose k} 64k s^{k-1} ds $$

$$ = {64 \choose k} 64 s^{k} $$

Then I differentiate it with respect to s? Wouldn't it become the form before integration?

 

[haruspex]

Then I differentiate it with respect to s?

Not yet. Sum it first.
The sequence is: multiply by s^k-1, integrate, perform the sum, differentiate wrt s, plug in s=1.

 

[songoku]

Not yet. Sum it first.
The sequence is: multiply by s^k-1, integrate, perform the sum, differentiate wrt s, plug in s=1.

So:
$$\int U_{k} ~ ds = {64 \choose k} 64 s^{k} $$
$$\sum_{k=0}^{k=64} \int U_{k} ~ ds =\sum_{k=0}^{k=64} {64 \choose k} 64 s^{k} $$
$$=64 ({64 \choose 0} s^{0} + {64 \choose 1} s^{1} + ... + {64 \choose 64} s^{64}) $$

Differentiate both sides with respect to s:
$$\sum_{k=0}^{k=64} U_{k} = {64 \choose 1} + 2 {64 \choose 2} s + 3 {64 \choose 3} s^{2} + ... + 64 {64 \choose 64} s^{63} $$

Put s = 1:
$$\sum_{k=0}^{k=64} U_{k} = {64 \choose 1} + 2 {64 \choose 2} + 3 {64 \choose 3} + ... + 64 {64 \choose 64} $$

Am I doing it correctly?

 

[haruspex]

Am I doing it correctly?

No, you have not performed the sum. You have left it as a Σ. It sums easily into a closed form.
You are familiar with the binomial theorem, yes?

 

[songoku]

No, you have not performed the sum. You have left it as a Σ. It sums easily into a closed form.
You are familiar with the binomial theorem, yes?

I have learned about binomial theorem but I am trying to figure out how to use it for this question.

Let me try again:
$$\int U_{k} ~ ds = {64 \choose k} 64 s^{k} $$
$$\sum_{k=0}^{k=64} \int U_{k} ~ ds =\sum_{k=0}^{k=64} {64 \choose k} 64 s^{k} $$
$$=64 (1+s)^{64}$$

Differentiate both sides with respect to s:
$$\sum_{k=0}^{k=64} U_{k} = 64^{2} (1+s)^{63}$$

Put s = 1:
$$\sum_{k=0}^{k=64} U_{k} = 64^{2} (2)^{63}$$
$$=2^{75}$$

Is this how I suppose to do it?

 

[haruspex]

I have learned about binomial theorem but I am trying to figure out how to use it for this question.

Let me try again:
$$\int U_{k} ~ ds = {64 \choose k} 64 s^{k} $$
$$\sum_{k=0}^{k=64} \int U_{k} ~ ds =\sum_{k=0}^{k=64} {64 \choose k} 64 s^{k} $$
$$=64 (1+s)^{64}$$

Differentiate both sides with respect to s:
$$\sum_{k=0}^{k=64} U_{k} = 64^{2} (1+s)^{63}$$

Put s = 1:
$$\sum_{k=0}^{k=64} U_{k} = 64^{2} (2)^{63}$$
$$=2^{75}$$

Is this how I suppose to do it?

You got it.

 

[songoku]

Thanks a lot for the help (Perok, Ray Vickson, haruspex)