1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Value of summation involving combination

  1. Oct 4, 2016 #1
    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. jcsd
  3. Oct 4, 2016 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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##
     
  4. Oct 4, 2016 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  5. Oct 4, 2016 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
  6. Oct 10, 2016 #5
    Maybe the pattern you are referring is the same as Ray Vickson?

    I get your hint. Thanks

    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
     
  7. Oct 10, 2016 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, that's the right step.
    Do you not recognise that sum? (Binomial Theorem.)
     
  8. Oct 11, 2016 #7
    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 $$
     
  9. Oct 11, 2016 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Keep it as an indefinite integral. You will need to differentiate wrt s later.
     
  10. Oct 11, 2016 #9
    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?
     
  11. Oct 11, 2016 #10

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Not yet. Sum it first.
    The sequence is: multiply by sk-1, integrate, perform the sum, differentiate wrt s, plug in s=1.
     
  12. Oct 11, 2016 #11
    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?
     
  13. Oct 11, 2016 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  14. Oct 17, 2016 #13
    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?
     
  15. Oct 17, 2016 #14

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You got it.
     
  16. Oct 17, 2016 #15
    Thanks a lot for the help (Perok, Ray Vickson, haruspex)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted