shubhamsrg
  • shubhamsrg
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 ?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
shubhamsrg
  • shubhamsrg
i mean can we arrive at sum of n digits formula using permutation/combination/binomial ?
KingGeorge
  • KingGeorge
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.
ParthKohli
  • ParthKohli
\[C(n + 1, 2) = \dfrac{(n + 1)!}{(n - 1)!2!} = \dfrac{(n + 1)n\cancel{(n -1)!}}{\cancel{(n -1)!}2!}\]

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

KingGeorge
  • KingGeorge
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.
shubhamsrg
  • shubhamsrg
we are selecting 2 objects from n+1 things, okay, what do you mean by having n+1 choices for first thing ?
ParthKohli
  • ParthKohli
And then there's a proof without words:
1 Attachment
KingGeorge
  • KingGeorge
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.
shubhamsrg
  • shubhamsrg
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. ?
KingGeorge
  • KingGeorge
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}\).
KingGeorge
  • KingGeorge
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.
shubhamsrg
  • shubhamsrg
C(n,2) = 1+2+3...(n-1) -->am stuck here..
shubhamsrg
  • shubhamsrg
thats actually my question only if you replace n by n-1 .. :P
shubhamsrg
  • shubhamsrg
i mean n by n+1
KingGeorge
  • KingGeorge
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\]
shubhamsrg
  • shubhamsrg
ohh..got it!! :O
shubhamsrg
  • shubhamsrg
should have understood in the first attempt only..hmm my bad! thanks again..! :)
ParthKohli
  • ParthKohli
@KingGeorge: Quick question... can you use the Binomial Theorem here? ;)
KingGeorge
  • KingGeorge
I'm not sure. The issue with the binomial theorem, is that you get every \(\binom{n}{k}\) for \(0\le k\le n\).
ParthKohli
  • ParthKohli
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\)
UnkleRhaukus
  • UnkleRhaukus
\[ \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}\]
ParthKohli
  • ParthKohli
Wow!!
shubhamsrg
  • shubhamsrg
i didnt understand @UnkleRhaukus area is okay,how do you relate sum of digits ?
ParthKohli
  • ParthKohli
@shubhamsrg: \(\underbrace{1 + 2 + 3 + 4 \cdots n}_{h} + \underbrace{0 + 0 + 0\cdots}_{b}\)
KingGeorge
  • KingGeorge
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.
KingGeorge
  • KingGeorge
Also, @UnkleRhaukus, there are n+1 rows in that diagram, not n.
shubhamsrg
  • shubhamsrg
so you;re saying area = (1+2+3..n) + (0+0...(n+1 times) )
UnkleRhaukus
  • UnkleRhaukus
oh bother
ParthKohli
  • ParthKohli
But the geometric proofs are really pretty. =)
shubhamsrg
  • shubhamsrg
i did not, follow the geometric proof .. ?
shubhamsrg
  • shubhamsrg
by not follow i mean didnt get*
shubhamsrg
  • shubhamsrg
@UnkleRhaukus ? @ParthKohli ?
ParthKohli
  • ParthKohli
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...
ParthKohli
  • ParthKohli
half the base times height*
shubhamsrg
  • shubhamsrg
got it! B|
shubhamsrg
  • shubhamsrg
that was really cool..thanks @UnkleRhaukus @ParthKohli and surely @KingGeorge
KingGeorge
  • KingGeorge
You're very welcome.
ParthKohli
  • ParthKohli
:)
shubhamsrg
  • shubhamsrg
ohh wait
ParthKohli
  • ParthKohli
Yes, correction: it's the sum of the first \(n\) natural numbers.
shubhamsrg
  • shubhamsrg
(n+1) + n + n-1 ... 1 = (n+2)(n+1)/2 also, in the figure, height = n+1
ParthKohli
  • ParthKohli
Yes, so the height is just the first \(h\) natural numbers.
ParthKohli
  • ParthKohli
But if we assume that \(n +1 = h\), then we have \(h(h+1)/2\)
shubhamsrg
  • shubhamsrg
height = n+1 base =n +1 so area accordingly = (n+1)^2 /2
shubhamsrg
  • shubhamsrg
0,1,2...n -->n+1 units 0 also written n+1 times.. hmm ?
ParthKohli
  • ParthKohli
Yeah...
ParthKohli
  • ParthKohli
But @KingGeorge pointed out a mistake earlier. Not sure how I should comprehend the diagram ._.
UnkleRhaukus
  • UnkleRhaukus
\[\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\]
UnkleRhaukus
  • UnkleRhaukus
the sum of the first \(n\)-natural numbers starting at (n=1,0)
shubhamsrg
  • shubhamsrg
no..following the pattern, n-1 should have been written 2 times..
shubhamsrg
  • shubhamsrg
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
shubhamsrg
  • shubhamsrg
so whats the flaw in geometrical proof ? please get back to this..
shubhamsrg
  • shubhamsrg
as the geometrical proof seems correct, but shouldnt have been correct! :|
KingGeorge
  • KingGeorge
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).
KingGeorge
  • KingGeorge
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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.