proof by induction

Technology and Gaming Help and Support
#1

Hello all,
I have the following problem to solve:

the count of 2-element subsets of a n-element set is (n(n-1)) / 2.

now I should prove that with an induction proof and case differntiation.
How to do this?
I mean the first step is easy, just n=1 and done, but the inductionstep with case differentiation…

Any ideas?

#2

just to make sure, you’re asking a forum for help with your homework, right?

#3

inb4 about seven

#4

ah well, alright.
an idea how to start the induction step would be enough, I don’t want you to solve the whole thing, I just need some help how to start.

#5

A little hint: You want to find the number of subsets of cardinality 2 in a set M of n+1 elements.
Choose an element x \in M. Now you know that the number of subsets of M of two elements is equal to the number of subsets of M{x} of two elements plus the number of subsets of M of two elements where one of the elements is x.

#6

Well, either the teacher explaining this to you explained it wrongly, or you didn’t pay enough attention.

Usually the first step is chosen in such a way that it actually gives meaningful result. Since a 1-element set cannot have 2-element subsets, it makes more sense to select first step being n=2.

Now, for n=2, there’s only 1 such subset (both of the elements), so 2*1/2 = 1 is correct answer.

Now the induction step:
Assume the theorem is valid for some n=k. Does that make it valid for n=k+1?

Proof:
The addition of 1 new element does not, in any way, change any of the already constructable (construable?) 2-element subsets that were in the k-element set, so the only difference can and will result from the newly added element x. The new element x has k other elements (the original elements) with which it can form a 2-element subset, and all these possible pairs must be added.
So, the original set had k*(k-1)/2 2-element subsets, and we’re adding k new such subsets:
k*(k-1)/2 + k

k*(k-1)/2 + 2k/2

[k*(k-1) + 2k ] / 2

[k*(k-1) + k*(2)] / 2
notice the parts in “( )”

k * [(k-1)+(2)] ___ / 2

k * (k+1) / 2
and since the new set has “k+1” elements (let’s call this j, j=k+1)

(j * (j-1)) / 2

QED

#7

@MysticJ:
woah, thank you very much!
btw, I began with n=2 in my proof, don’t know why I typed 1 in my post.
anyways, I think I finally understood how this works now.

#8

My pleasure.

#9

I wish the Black Mesa Forum had been around when I had to do homework. :[

Founded in 2004, Leakfree.org became one of the first online communities dedicated to Valve’s Source engine development. It is more famously known for the formation of Black Mesa: Source under the 'Leakfree Modification Team' handle in September 2004.