Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A set A of n elements has n(n-1)/2 subsets of 2 elements

  1. Dec 11, 2011 #1
    I would very much like some help to the following problem.

    1. The problem statement, all variables and given/known data

    Using mathematical induction, prove that a finite set A of n elements has n(n-1)/2 subsets of two elements.

    3. The attempt at a solution

    * Base step n=2: 2(2-1)/2= 1 subset of two elements.
    * Inductive step: assuming the statement holds for n=k, that is a set A of k elements has k(k-1)/2 (hypothesis)
    We want to show that it also holds for n=k+1, that is a set A of k+1 has (k+1)(k+1-1)/2 elements.
    How can we infer from the hypothesis ??? I have no idea ...

    I have an engineering background so be as descriptive as you can.
    Thank you in advance.
  2. jcsd
  3. Dec 11, 2011 #2


    User Avatar
    Homework Helper

    A set A of k elements has k(k-1)/2 subsets of two elements, as you said.
    Suppose you add a new element to set A. How many new subsets can be created where one of the elements of these subsets is the new element?
  4. Dec 11, 2011 #3
    if we add an element to the set which previously had k elements (that is now has k+1 elements) the new subsets that include the new element will be :

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

    So, how can we argue that this will solve the problem ?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook