Math CentralQuandaries & Queries


Question from Snehal, a student:

1. Let an denote the number of subsets of f{1,2, 3.... n}including the empty set and the set itself.)
a) Show an = 2an-1
b) Guess a formula for the value of an and use induction to prove you are right


1. Each time you add a member to the set (in other words each time n increases by one), all the previous subsets still exist which do not include the number n, but now you can add the element n to each of them. This doubles the number of possible sets.

2. Hint: Think in binary: each member may be either in the subset or not in the subset. How many members are there? For help with the induction part of the question, take a look at our other induction questions in our archive for examples.

Stephen La Rocque.

About Math Central


Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.
Quandaries & Queries page Home page University of Regina PIMS