Results 1 to 7 of 7

Thread: 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,577
    Thanks
    790
    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 $\displaystyle (A\cup B)^c\subseteq A^c\cap B^c$ and $\displaystyle 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,577
    Thanks
    790
    Ok the linear homogeneous recurrence relations with constant coefficients is still a bit confusing from wiki.
    Take the equation $\displaystyle a_k = 2a_{k-1} + 3a_{k-2}$. Replace $\displaystyle a_k$ by $\displaystyle x^k$ for some variable x; you get $\displaystyle x^k=2x^{k-1}+3x^{k-2}$. Divide both sides by $\displaystyle x^{k-2}$ to get $\displaystyle x^2=2x+3$. This is called the characteristic equation of the original equation. Solving it gives you two roots $\displaystyle x_1$ and $\displaystyle x_2$. The solution to the original equation is $\displaystyle 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 $\displaystyle a_k=Cx_1^k+Dx_2^k$ and use the given $\displaystyle a_0$ and $\displaystyle 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 $\displaystyle a_k = 2a_{k-1} + 3a_{k-2}$. Replace $\displaystyle a_k$ by $\displaystyle x^k$ for some variable x; you get $\displaystyle x^k=2x^{k-1}+3x^{k-2}$. Divide both sides by $\displaystyle x^{k-2}$ to get $\displaystyle x^2=2x+3$. This is called the characteristic equation of the original equation. Solving it gives you two roots $\displaystyle x_1$ and $\displaystyle x_2$. The solution to the original equation is $\displaystyle 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 $\displaystyle a_k=Cx_1^k+Dx_2^k$ and use the given $\displaystyle a_0$ and $\displaystyle 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
    12,028
    Thanks
    848

    Wink

    Hello, hellfire127!

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

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


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

    . . $\displaystyle \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}$


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

    You are correct: .$\displaystyle 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: .$\displaystyle a_k - 2a_{k-1} - 3a_{k-2} \:=\:0$

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

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

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

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

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

    Form a linear combination: .$\displaystyle 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:

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

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


    Therefore: .$\displaystyle \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: Nov 5th 2011, 09:29 AM
  2. Formula for the sequence
    Posted in the Calculus Forum
    Replies: 8
    Last Post: Sep 22nd 2011, 07:54 PM
  3. Replies: 4
    Last Post: Jul 15th 2011, 01:30 PM
  4. Replies: 2
    Last Post: Aug 28th 2009, 02:59 AM
  5. formula for a sequence
    Posted in the Differential Geometry Forum
    Replies: 16
    Last Post: Jul 5th 2009, 10:07 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum