Results 1 to 7 of 7

Math Help - Formula for sequence and Prove de Morgan's law for unions

  1. #1
    Junior Member
    Joined
    Oct 2010
    Posts
    43

    Formula for sequence and Prove de Morgan's law for unions

    I'm trying figure out a formula that would work with this sequence defined by a0=1, a1=2, and ak = 2ak-1 + 3ak-2, for all integers k is equal or greater than 2.

    I found the values for the rest of the a subscripts
    a2 = 7
    a3 = 20
    a4 = 61
    a5 = 182
    Seems like it's the values are 3 times more than previous value plus 1 or minus 1

    As for de Morgan's law for unions.
    If A and B are subsets of the universal set U, then (AUB)^c = (A^c)⋂(B^c).

    Would i prove this law by showing a universal set then select random values from the universal set to set A and set B? After I would show AUB, A^c, B^c, etc all the way to (AUB)^c = (A^c)⋂(B^c)?

    or would i need to prove this by some form of induction?....
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    I'm trying figure out a formula that would work with this sequence defined by a0=1, a1=2, and ak = 2ak-1 + 3ak-2, for all integers k is equal or greater than 2.
    This is a so-called linear homogeneous recurrence relations with constant coefficients. See further down the same page how to solve it.

    If A and B are subsets of the universal set U, then (AUB)^c = (A^c)⋂(B^c).
    You can see this from a Venn diagram. Or you follow the usual method: proving (A\cup B)^c\subseteq A^c\cap B^c and A^c\cap B^c\subseteq (A\cup B)^c. For each inclusion, assume that some x is in the smaller set; then you need to show that x is in the bigger set.

    Edit.
    or would i need to prove this by some form of induction?....
    No, one proves by induction facts about objects that are inductively generated. For example, natural numbers are generated from 0 by repeatedly applying "plus one" function. Sets in general are not generated gradually in this way, so one can't use induction here.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    Ok the linear homogeneous recurrence relations with constant coefficients is still a bit confusing from wiki. My book has a smiliar example but doesn't really show how to obtain a formula by it.

    Also, is the Fibonacci squence similar for this problem?

    Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
    (Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    Ok the linear homogeneous recurrence relations with constant coefficients is still a bit confusing from wiki.
    Take the equation a_k = 2a_{k-1} + 3a_{k-2}. Replace a_k by x^k for some variable x; you get x^k=2x^{k-1}+3x^{k-2}. Divide both sides by x^{k-2} to get x^2=2x+3. This is called the characteristic equation of the original equation. Solving it gives you two roots x_1 and x_2. The solution to the original equation is a_k=Cx_1^k+Dx_2^k for some constants C and D. To find C and D, substitute k = 0 and k = 1 in a_k=Cx_1^k+Dx_2^k and use the given a_0 and a_1.

    Also, is the Fibonacci sequence similar for this problem?
    Yes.

    Suppose Fn, n is greater or equal to 0 is the Fibonacci sequence (i.e. F0=F1 = 1, and Fn = Fn-1 + Fn-2 for n is greater or equal to 2). Use mathematical induction to prove that
    (Fn+2)(Fn)-F^2 * n+1 = (-1)^n for all n greater or equal to 0.
    It is recommended to start a new thread for new questions. See rules #8 and 9 here.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    Quote Originally Posted by emakarov View Post
    Take the equation a_k = 2a_{k-1} + 3a_{k-2}. Replace a_k by x^k for some variable x; you get x^k=2x^{k-1}+3x^{k-2}. Divide both sides by x^{k-2} to get x^2=2x+3. This is called the characteristic equation of the original equation. Solving it gives you two roots x_1 and x_2. The solution to the original equation is a_k=Cx_1^k+Dx_2^k for some constants C and D. To find C and D, substitute k = 0 and k = 1 in a_k=Cx_1^k+Dx_2^k and use the given a_0 and a_1.

    Yes.

    It is recommended to start a new thread for new questions. See rules #8 and 9 here.
    Thanks, yeah I'll start a new thread if I have problem with that question sorry. I need to work out the first one first. Will be back, thanks.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Oct 2010
    Posts
    43
    is the answer:

    (3/4)*3^k + (1/4)*(-1)^k ?

    is there a simplified version of it?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    644

    Wink

    Hello, hellfire127!

    \text{Find a formula for the sequence de{f}ined by:}

     a_0=1,\; a_1=2,\text{ and }a_k \,=\, 2a_{k-1} + 3a_{k-2},\text{ for all integers }k \ge 2.


    \text{I found the values for the rest of the }a_n:

    . . \begin{array}{ccc}a_0 &=& 1 \\ a_1 &=& 2 \\a_2 &=& 7 \\ a_3 &=& 20 \\ a_4 &=& 61 \\ a_5 &=& 182 \\ \vdots && \vdots\end{array}


    \text{Seems like the values are 3 times the previous value plus 1 or minus 1}
    . . Good!

    You are correct: . a_n \;=\;3a_{n-1} + (-1)^n
    . . Yet this is just another recurrence relation, not a "closed form".
    [But you can be proud of seeing that relationship.]

    Here is one procedure for finding the closed form . . .


    We have: . a_k  - 2a_{k-1} - 3a_{k-2} \:=\:0

    Let X^k \,=\,a_k
    . . We conjecture that the function is exponential.

    Then we have: . X^k - 2X^{k-1} - 3X^k \:=\:0

    Divide by X^{k-2}\!:\;\;X^2 - 2X - 3 \:=\:0

    . . . . . . . . . . . (X - 3)(X + 1) \:=\:0 \quad\Rightarrow\quad X \:=\:3,\,\text{-}1

    We have two functions: . 3^n\,\text{ and }\,(\text{-}1)^n

    Form a linear combination: . f(n) \;=\;A\!\cdot\!3^n + B\!\cdot\!(\text{-}1)^n


    Use the first two terms of the sequence and form a system of equations:

    . \begin{array}{ccccccccc}<br />
f(0) = 1\!: & A + B &=& 1 \\ f(1) = 2\!: & 3A - B ^&=& 2 \end{array}

    Solve the system: . A = \frac{3}{4},\:B = \frac{1}{4}


    Therefore: . \boxed{f(n) \;=\;\tfrac{3}{4}\left(3^n\right) + \tfrac{1}{4}(\text{-}1)^n}



    Edit: Ah . . . emakarov beat me to it.
    . . . .Will I delete all this? . . . No way!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. formula of a sequence ...
    Posted in the Algebra Forum
    Replies: 12
    Last Post: November 5th 2011, 09:29 AM
  2. Formula for the sequence
    Posted in the Calculus Forum
    Replies: 8
    Last Post: September 22nd 2011, 07:54 PM
  3. Replies: 4
    Last Post: July 15th 2011, 01:30 PM
  4. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  5. formula for a sequence
    Posted in the Differential Geometry Forum
    Replies: 16
    Last Post: July 5th 2009, 10:07 AM

Search Tags


/mathhelpforum @mathhelpforum