# 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 $(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.

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

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

6. is the answer:

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

is there a simplified version of it?

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