Prove that number of subsets of a set containing n distinct elements i

1.	Prove that number of subsets of a set containing n distinct elements is 2n, for all n ϵ N.
Answer» To prove; Number of subsets of a set containing n distinct elements is 2ⁿ. For a null set there is only one element Φ and therefore only one subset. ⇒ at n = 0 number of subsets = 1 = 2⁰ By considering a set with 1 element there will be 2 subsets with 1 and Φ ⇒ at n = 0 number of subsets = 2 = 2² By considering a set S_k with k element Let at n = k number of subsets = 2^k be true. For a set S_k+1 containing k+1 element The extra one element in set S_k+1 when compared with S_k will form an extra collection of subsets by combing with the existing 2^k subsets and as a result an extra 2^k subsets are formed. ⇒ at n = k+1 number of subsets = 2^k + 2^k = 2.2^k = 2^k+1 ⇒ P(k+1) is true. ∴ By Mathematical Induction number of subsets of a set containing n distinct elements is 2ⁿ, for all n ϵ N.

Prove that number of subsets of a set containing n distinct elements is 2n, for all n ϵ N.

Answer»

To prove; Number of subsets of a set containing n distinct elements is 2ⁿ.

For a null set there is only one element Φ and therefore only one subset.

⇒ at n = 0 number of subsets = 1 = 2⁰

By considering a set with 1 element there will be 2 subsets with 1 and Φ

⇒ at n = 0 number of subsets = 2 = 2²

By considering a set S_k with k element

Let at n = k number of subsets = 2^k be true.

For a set S_k+1 containing k+1 element

The extra one element in set S_k+1 when compared with S_k will form an extra collection of subsets by combing with the existing 2^k subsets and as a result an extra 2^k subsets are formed.

⇒ at n = k+1 number of subsets = 2^k + 2^k = 2.2^k = 2^k+1

⇒ P(k+1) is true.

∴ By Mathematical Induction number of subsets of a set containing n distinct elements is 2ⁿ, for all n ϵ N.

Discussion

No Comment Found

Related InterviewSolutions

What were the two main occupations of the Rig Vedic Aryans?
Name the two political institutions which exercised check on the powers of the King in the Rig Vedic period.
What w’as the position of women in the Rig Vedic age ?
Describe the social life of the Rig Vedic Aryans with reference to the following: (a) The Family Structure (b) Position of Women (c) Varna System
With reference to the following explain the main features of the Rig Vedic Economy: (a) Agriculture (b) Domestication of Animals (c) Trade Transactions, Crafts and Transportation
Mention any two archaeological sources to reconstruct the later Vedic Age.
Mention any two of the Ashrams in the life of a man in Aryan society.
What information do we gather from the later Vedic literature in respect of: (a) Spread of Vedic Civilization to many New Regions. (b) Role of Iron in later Vedic Economy.
Mention briefly the rituals and sacrifices of the later Vedic Aryans?
What is the message of the Bhagavad Gita?