View Single Post
eumyang
eumyang is offline
#2
Dec11-11, 01:26 PM
HW Helper
P: 1,347
Quote Quote by dpesios View Post
* 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.
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?