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

**hellfire127** · November 30th 2010, 10:09 AM

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

**emakarov** · November 30th 2010, 10:25 AM

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.

**hellfire127** · November 30th 2010, 10:50 AM

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.

**emakarov** · November 30th 2010, 11:34 AM

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.

**hellfire127** · November 30th 2010, 11:45 AM

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.

**hellfire127** · November 30th 2010, 12:13 PM

is the answer:

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

is there a simplified version of it?

**Soroban** · November 30th 2010, 04:22 PM

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!

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

formula of a sequence ...

Formula for the sequence

how do you prove determinant expand by the Leibniz formula or the Laplace formula ...

prove that if sequence (an) converges, use def of limit of sequence to prove...

formula for a sequence

Search Tags