Question

सभी n ∈ N के लिए, सिद्ध कीजिए कि n भिन्न-भिन्न distinct अवयव वाले (अंतर्विष्ट किए हुए) समुच्चय के उपसमुच्चयों की संख्या 2ⁿ है।

Answer 1

देखिए P(n) भिन्न अवयव वाले समुच्चय के उपसमुच्चयों की संख्या 2ⁿ, ∀ n ∈ N है।

उस पर गौर करें, n = 1 के लिये P(1) यह सच है।

इसलिए, उपसमुच्चय की संख्या = 2¹ = 2 सच माना जाता है क्योंकि उपसमुच्चय की संख्या इसलिए, P(1) के लिए यह सच है।

ध्यान मे लो की, n = k के लिए P(k) सच माना जाता है क्योंकि उपसमुच्चय की संख्या 2k है।

इसलिए, P(k) यह भी सच होना चाहिए।

P(k + 1) के लिए हल,

⇒ P(k + 1) = 2^{k + 1}

यह जान लें कि, यदि दिए गए समुच्चय के तत्वों में एक संख्या को जोड़ा जाता है, तो उपसमुच्चयों की संख्या दोगुनी हो जाती है।

इसलिए, अलग अवयव वाले = `2 × 2^k = 2^{k + 1}` समुच्चय के उपसमुच्चयों की संख्या (k + 1)।

इसलिए, जब भी P(k) सत्य हो, P(k + 1) सत्य है।

यह साबित हो जाता है कि, एक समुच्चय के उपसमुच्चयों की संख्या जिसमें n अलग-अलग अवयव हैं, सभी प्राकृतिक संख्याओं के लिए 2ⁿ सही है।