# Thread: Formula for sequence and Prove de Morgan's law for unions

1. ## 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?....

2. 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.

3. 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.

4. 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.

5. Originally Posted by emakarov
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.

6. is the answer:

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

is there a simplified version of it?

7. 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!