Question

Please help me solve this Question from mathematical induction from Course Elemantary Number Theory :

If S is a set, we denoted the number of elements it has by |S|. Prove that if |S|= n , then ∑T⊆s 2|T| = 3n

Answer 1

8

bataineh
Please help me solve this Question from mathematical induction from Course Elemantary Number Theory

Answer 2

8

bataineh
Please help me solve this Question from mathematical induction from Course Elemantary Number Theory

Answer 3

As an hint, it is a well-known result that \[
\sum_{S\subseteq E} |T| = n2^{n-1} \]
It can be proven by noting that :
\[ \sum_{S\subseteq E} |T| = \sum_{k=0}^{n} k \binom{n}{k} \]

Answer 4

(In the previous identity, E is your S set, and S a subset.)
It is also relevant to know that 2^n is the cadinality of the power set (the set of all subset) of a set of n element.