# Value of summation involving combination

1. Oct 4, 2016

### songoku

1. The problem statement, all variables and given/known data
Find

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

2. Relevant equations
Not sure

3. The attempt at a solution
Please give me hint how to start doing this question

2. Oct 4, 2016

### PeroK

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$

3. Oct 4, 2016

### 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 kth 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.

4. Oct 4, 2016

### 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?

Last edited by a moderator: Oct 4, 2016
5. Oct 10, 2016

### songoku

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

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 sk-1 and after integration with respect to s, I get 64Ck . 64 . sk
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

6. Oct 10, 2016

### haruspex

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

7. Oct 11, 2016

### songoku

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

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 64Ck . 64k as Uk.

Uk = 64Ck . 64k

Then multiplying the term with sk-1, it becomes:

Uk = 64Ck . 64k . sk-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$$

8. Oct 11, 2016

### haruspex

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

9. Oct 11, 2016

### songoku

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?

10. Oct 11, 2016

### haruspex

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

11. Oct 11, 2016

### songoku

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?

12. Oct 11, 2016

### haruspex

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?

13. Oct 17, 2016

### songoku

I have learnt 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?

14. Oct 17, 2016

### haruspex

You got it.

15. Oct 17, 2016

### songoku

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