A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 2 years ago
sum of first natural nos. = n(n+1)/2
my question is that is it just a coincidence that this sum is also equal to C(n+1 ,2) ? or is there a theoretical explanation for this ?
 2 years ago
sum of first natural nos. = n(n+1)/2 my question is that is it just a coincidence that this sum is also equal to C(n+1 ,2) ? or is there a theoretical explanation for this ?

This Question is Closed

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2i mean can we arrive at sum of n digits formula using permutation/combination/binomial ?

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6Well, recursively, you can see that \[\binom{n+1}{2}=\binom{n}{2}+\binom{n}{1}=\sum_{i=0}^{n1}i+n\]So the result follows easily from induction.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1\[C(n + 1, 2) = \dfrac{(n + 1)!}{(n  1)!2!} = \dfrac{(n + 1)n\cancel{(n 1)!}}{\cancel{(n 1)!}2!}\]

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6Also, 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.

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2we are selecting 2 objects from n+1 things, okay, what do you mean by having n+1 choices for first thing ?

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1And then there's a proof without words:

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6We 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.

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2hmm 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. ?

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6That 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}\).

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6I 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.

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2C(n,2) = 1+2+3...(n1) >am stuck here..

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2thats actually my question only if you replace n by n1 .. :P

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6The first proof I gave shows that. Take 5choose2 for example.\[\binom{5}{2}=\binom{4}{2}+\binom41=\binom32+\binom31+4=\binom22+\binom21+3+4=1+2+3+4\]

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2should have understood in the first attempt only..hmm my bad! thanks again..! :)

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1@KingGeorge: Quick question... can you use the Binomial Theorem here? ;)

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6I'm not sure. The issue with the binomial theorem, is that you get every \(\binom{n}{k}\) for \(0\le k\le n\).

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1I see that there's a really cool proof to \(\binom{n}{0} +\binom{n}{1}+ \binom{n}{2} \cdots\binom{n}{n} = 2^n\)

UnkleRhaukus
 2 years ago
Best ResponseYou've already chosen the best response.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}\]

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2i didnt understand @UnkleRhaukus area is okay,how do you relate sum of digits ?

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1@shubhamsrg: \(\underbrace{1 + 2 + 3 + 4 \cdots n}_{h} + \underbrace{0 + 0 + 0\cdots}_{b}\)

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6If 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.

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6Also, @UnkleRhaukus, there are n+1 rows in that diagram, not n.

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2so you;re saying area = (1+2+3..n) + (0+0...(n+1 times) )

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1But the geometric proofs are really pretty. =)

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2i did not, follow the geometric proof .. ?

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2by not follow i mean didnt get*

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2@UnkleRhaukus ? @ParthKohli ?

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1When 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...

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1half the base times height*

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2that was really cool..thanks @UnkleRhaukus @ParthKohli and surely @KingGeorge

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6You're very welcome.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1Yes, correction: it's the sum of the first \(n\) natural numbers.

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2(n+1) + n + n1 ... 1 = (n+2)(n+1)/2 also, in the figure, height = n+1

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1Yes, so the height is just the first \(h\) natural numbers.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1But if we assume that \(n +1 = h\), then we have \(h(h+1)/2\)

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2height = n+1 base =n +1 so area accordingly = (n+1)^2 /2

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.20,1,2...n >n+1 units 0 also written n+1 times.. hmm ?

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.1But @KingGeorge pointed out a mistake earlier. Not sure how I should comprehend the diagram ._.

UnkleRhaukus
 2 years ago
Best ResponseYou've already chosen the best response.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\\&&&&&n1\end{array}{}}\right\}}\small n\]

UnkleRhaukus
 2 years ago
Best ResponseYou've already chosen the best response.2the sum of the first \(n\)natural numbers starting at (n=1,0)

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2no..following the pattern, n1 should have been written 2 times..

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.20 is written n+1 times 1 > n times =>sum is n+1 2>n1 times =>sum is n+1 . . .n1 > 2 times =>sum should be n+1

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2so whats the flaw in geometrical proof ? please get back to this..

shubhamsrg
 2 years ago
Best ResponseYou've already chosen the best response.2as the geometrical proof seems correct, but shouldnt have been correct! :

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6I 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+...+n1 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 n1 is the same as C(n,2).

KingGeorge
 2 years ago
Best ResponseYou've already chosen the best response.6The 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.
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.