6. Discover the recursive formula for Hn. Find Hn for n=1,2,3...6. Based on these values you will be able toseethe recursive pattern. proving the formula is optional for extra credit.Consider all subsets of N={1, 2, 3,..., n).How many of these subsets, SC N, satisfy the property that(i)Vx (x ES → x +1 ¢ S) ?Denote the number of subsets satisfying this property (i) by Hn.(a) Find the first 6 values of Hn . I have calculated n=1 and n=2, so you need to do n=3, 4, 5, 6(b) Find and prove the recursive formula for the sequence Hn .Example: Let n=1. Then N={1} and the subsets satisfying property (i) are {1} and O so H1=2.Let n=2. Then N={1,2} and the subsets satisfying property (i) are {1}, {2}, and Ø, i.e. H3=3.Note: {1,2} is also subset of {1,2} but since for x=1, x+1=2 and both 1 and 2 are contained in{1,2} therefore the set {1,2} fails to satisfy property (i).7. Prove by induction that the number of subsets for a set with n elements is 2^n.

Given that N=1, 2, 3, ..., n We know the total number of subset of a set is 2n, where n is the number of element in set. Solution 6(a): For n=3, N=1, 2, 3 number of subsets of N are 23=8 which are ϕ, 1, 2, 3, 1, 2, 1, 3, 2, 3, 1, 2, 3. The set satisfying the property (i) ∀x x∈S→x+1∉S are ϕ, 1, 2, 3, 1, 3. So, H3=5. Similarly, for n=4, N=1, 2, 3, 4 number of subsets are 24=16 which are ϕ, 1, 2, 3, 4, 1,2, 1,3, 1,4, 2,3, 2,4, 3,4, 1,2,3, 1,2,4, 1,3,4, 2,3,4, 1,2,3,4. The set satisfying the property (i) ∀x x∈S→x+1∉S are ϕ, 1, 2, 3, 4, 1,3, 1,4, 2,4. So, H4=8. Similarly for n=5, N=1, 2, 3, 4, 5 the subset satisfying the given property ∀x x∈S→x+1∉S are ϕ, 1, 2, 3, 4, {5}, 1,3, 1,4, {1,5}, 2,4, 2,5, 3,5. So H5=12. for n=6, N=1, 2, 3, 4, 5, 6 the subset satisfying the given property ∀x x∈S→x+1∉S are ϕ, 1, 2, 3, 4, {5}, 6, 1,3, 1,4, {1,5}, 1,6, 2,4, 2,5, 2,6, 3,5, 3,6, 4,6. So H5=17. Solution of 6(b) Therefore sequence of Hn is 2, 3, 5, 8, 12, 17, ... Therefore recursive formula is Hn+1=Hn+n. For n=1, H2=H1+1=2+1=3. n=2, H3=H2+2=3+2=5 n=3, H4=H3+3=5+3=8 n=4, H5=H4+4=8+4=12 n=5, H6=H5+5=12+5=17