Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

shubhamsrg Group Title

sum of first natural nos. = n(n+1)/2 my question is that is it just a co-incidence that this sum is also equal to C(n+1 ,2) ? or is there a theoretical explanation for this ?

  • one year ago
  • one year ago

  • This Question is Closed
  1. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i mean can we arrive at sum of n digits formula using permutation/combination/binomial ?

    • one year ago
  2. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    Well, recursively, you can see that \[\binom{n+1}{2}=\binom{n}{2}+\binom{n}{1}=\sum_{i=0}^{n-1}i+n\]So the result follows easily from induction.

    • one year ago
  3. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    \[C(n + 1, 2) = \dfrac{(n + 1)!}{(n - 1)!2!} = \dfrac{(n + 1)n\cancel{(n -1)!}}{\cancel{(n -1)!}2!}\]

    • one year ago
  4. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    Also, suppose you have \(n+1\) objects to choose 2 things from, but order doesn't matter. Then you have \(n+1\) choices for the first thing, and \(n\) choices for the second. but since order doesn't matter, you have to divide by \(2!=2\). Resulting in \[\frac{(n+1)\cdot n}{2}\]Basically what parth just did above me.

    • one year ago
  5. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    we are selecting 2 objects from n+1 things, okay, what do you mean by having n+1 choices for first thing ?

    • one year ago
  6. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    And then there's a proof without words:

    • one year ago
    1 Attachment
  7. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    We have a total of \(n+1\) objects, and we can choose any of them for our first choice. Thus, we have a total of \(n+1\) choices since every object can be chosen.

    • one year ago
  8. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    hmm so we have n+1 choices for first one n for second so total combinations = n(n+1)/2! okay, fair enough how you relate that to sum of n natural nos. ?

    • one year ago
  9. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    That explanation isn't very well connected to the sum of n natural numbers. However, the first explanation that I gave is probably a better explanation of what you're looking for. The base case is \(\displaystyle\binom{2}{2}\), and after that, the result follows from the definition of \(\displaystyle\binom{n}{k}\).

    • one year ago
  10. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    I don't have any solid explanation of any inherent reason that \(\binom{2}{2}\) is the same as the sum of the natural numbers starting and ending at 1, other than coincidence.

    • one year ago
  11. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    C(n,2) = 1+2+3...(n-1) -->am stuck here..

    • one year ago
  12. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    thats actually my question only if you replace n by n-1 .. :P

    • one year ago
  13. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i mean n by n+1

    • one year ago
  14. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    The first proof I gave shows that. Take 5-choose-2 for example.\[\binom{5}{2}=\binom{4}{2}+\binom41=\binom32+\binom31+4=\binom22+\binom21+3+4=1+2+3+4\]

    • one year ago
  15. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    ohh..got it!! :O

    • one year ago
  16. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    should have understood in the first attempt only..hmm my bad! thanks again..! :)

    • one year ago
  17. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @KingGeorge: Quick question... can you use the Binomial Theorem here? ;)

    • one year ago
  18. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    I'm not sure. The issue with the binomial theorem, is that you get every \(\binom{n}{k}\) for \(0\le k\le n\).

    • one year ago
  19. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I see that there's a really cool proof to \(\binom{n}{0} +\binom{n}{1}+ \binom{n}{2} \cdots\binom{n}{n} = 2^n\)

    • one year ago
  20. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    \[ \stackrel{n+1}{\overbrace{\left.\begin{array}{ccccc}0&0&0&0&\cdots &0\\&1&1&1&\cdots&1\\&&2&2&\cdots&2\\&&&3&\cdots&3\\&&&&\ddots&\vdots\\&&&&&n\end{array}\right\}n}{}}\] \[A_\triangle=\frac{hb}2=\frac{n(n+1)}{2}\]

    • one year ago
  21. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Wow!!

    • one year ago
  22. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i didnt understand @UnkleRhaukus area is okay,how do you relate sum of digits ?

    • one year ago
  23. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    @shubhamsrg: \(\underbrace{1 + 2 + 3 + 4 \cdots n}_{h} + \underbrace{0 + 0 + 0\cdots}_{b}\)

    • one year ago
  24. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    If we take \[(0+1)^2=\binom200^21^0+\binom210^11^1+\binom220^01^2=0+0+\binom22\]\[(0+1)^2=1^2=1\]So \[\binom22=1\]But I don't really see how this helps with that issue.

    • one year ago
  25. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    Also, @UnkleRhaukus, there are n+1 rows in that diagram, not n.

    • one year ago
  26. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    so you;re saying area = (1+2+3..n) + (0+0...(n+1 times) )

    • one year ago
  27. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    oh bother

    • one year ago
  28. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    But the geometric proofs are really pretty. =)

    • one year ago
  29. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    i did not, follow the geometric proof .. ?

    • one year ago
  30. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    by not follow i mean didnt get*

    • one year ago
  31. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    @UnkleRhaukus ? @ParthKohli ?

    • one year ago
  32. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    When you calculate the area of ANY figure, you count the number of units it covers. So just add the number of units (numbers) inside it: \((n + 1) + n + (n - 1) + (n - 2)\cdots 1 \) which is just the sum of first \(n + 1\) natural numbers. But the area ALSO equals base times height, so...

    • one year ago
  33. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    half the base times height*

    • one year ago
  34. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    got it! B|

    • one year ago
  35. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    that was really cool..thanks @UnkleRhaukus @ParthKohli and surely @KingGeorge

    • one year ago
  36. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    You're very welcome.

    • one year ago
  37. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    :)

    • one year ago
  38. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    ohh wait

    • one year ago
  39. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, correction: it's the sum of the first \(n\) natural numbers.

    • one year ago
  40. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    (n+1) + n + n-1 ... 1 = (n+2)(n+1)/2 also, in the figure, height = n+1

    • one year ago
  41. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yes, so the height is just the first \(h\) natural numbers.

    • one year ago
  42. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    But if we assume that \(n +1 = h\), then we have \(h(h+1)/2\)

    • one year ago
  43. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    height = n+1 base =n +1 so area accordingly = (n+1)^2 /2

    • one year ago
  44. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    0,1,2...n -->n+1 units 0 also written n+1 times.. hmm ?

    • one year ago
  45. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Yeah...

    • one year ago
  46. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    But @KingGeorge pointed out a mistake earlier. Not sure how I should comprehend the diagram ._.

    • one year ago
  47. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    \[\color{red}*\]\[\stackrel{n+1}{\left.\overbrace{\begin{array}{ccccc}0&0&0&0&\cdots &0\\&1&1&1&\cdots&1\\&&2&2&\cdots&2\\&&&3&\cdots&3\\&&&&\ddots&\vdots\\&&&&&n-1\end{array}{}}\right\}}\small n\]

    • one year ago
  48. UnkleRhaukus Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    the sum of the first \(n\)-natural numbers starting at (n=1,0)

    • one year ago
  49. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    no..following the pattern, n-1 should have been written 2 times..

    • one year ago
  50. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    0 is written n+1 times 1 -> n times =>sum is n+1 2->n-1 times =>sum is n+1 . . .n-1 -> 2 times =>sum should be n+1

    • one year ago
  51. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    so whats the flaw in geometrical proof ? please get back to this..

    • one year ago
  52. shubhamsrg Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    as the geometrical proof seems correct, but shouldnt have been correct! :|

    • one year ago
  53. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    I would like to take a moment and go back to the "proof without words" @ParthKohli posted. I just realized exactly what that was showing, and it draws a very nice bijection between the sum of the natural numbers and C(n,2). The bottom line has n dots, and above, you have 1+2+...+n-1 dots. Now, choose two dots on the bottom line, and draw two diagonal lines up so that they meet somewhere above. These lines will intersect in another dot. Similarly, if you choose some dot not in the bottom line, and draw two diagonal lines downward. Each of these lines will hit some dot in the bottom row and you get two dots of the n dots. This demonstrates a function with an inverse, so it's a bijection, and the sum of the natural numbers up to n-1 is the same as C(n,2).

    • one year ago
  54. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 6

    The advantage of this method, is that it takes care of the C(2,2) case that I had issues with because when you have 2 dots in the bottom row, there's still a row above with 1 dot, so C(2,2)=1.

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.