Results 1 to 3 of 3

Thread: please set up recurrence equation

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    6

    please set up recurrence equation

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    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$

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    6
    hello soroban,
    I understood your first answer for my question,but the second answer
    is not understood.How did you set up recurrence equation and
    put it in closure form.Is closure form is a solution for it?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic recurrence equation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Feb 9th 2011, 10:14 AM
  2. [SOLVED] Difference equation - recurrence relation
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: Aug 2nd 2010, 09:08 AM
  3. Help me with this recurrence equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jan 1st 2010, 07:41 AM
  4. Simple Recurrence Equation Help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 5th 2008, 11:48 AM
  5. Population recurrence equation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 10th 2008, 11:06 PM

Search Tags


/mathhelpforum @mathhelpforum