Let an be the number of subsets of {1,2,3,..n} with atleast 2 elements,n>=1.
i)what are the values of a1,a2,a3?
2)set up a recuurence for an and solve it.
Hello, Bhavani!
Let $\displaystyle a_n$ be the number of subsets of $\displaystyle \{1,2,3,\hdots n\}$
1) What are the values of: $\displaystyle a_1,\:a_2,\:a_3$ ?
For $\displaystyle n = 1$, we have: .$\displaystyle S \:=\:\{1\}$
There are two subsets: .$\displaystyle \emptyset,\:\{1\}$
. . $\displaystyle a_1 = 2$
For $\displaystyle n=2$, we have: .$\displaystyle S \:=\:\{1,2\}$
There are four subsets: .$\displaystyle \emptyset,\:\{1\},\:\{2\},\:\{1,2\}$
. . $\displaystyle a_2 = 4$
For $\displaystyle n=3$, we have: .$\displaystyle S \:=\:\{1,2,3\}$
There are eight subsets: .$\displaystyle \emptyset,\:\{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\}$
. . $\displaystyle a_3 = 8$
2) Set up a recurrence for $\displaystyle a_n$ and solve it.
The recurrence is: .$\displaystyle a_n \;=\;2\cdot a_{n-1},\quad a_1 = 2$
The closed form is: .$\displaystyle a_n \:=\:2^n$