Results 1 to 6 of 6

- Jul 12th 2010, 04:43 PM #1

- Joined
- Feb 2010
- From
- Canada
- Posts
- 15

- Jul 12th 2010, 05:53 PM #2

- Joined
- Apr 2009
- From
- México
- Posts
- 721

- Jul 12th 2010, 06:40 PM #3

- Joined
- Feb 2010
- From
- Canada
- Posts
- 15

- Jul 13th 2010, 08:32 AM #4

- Joined
- Apr 2009
- From
- México
- Posts
- 721

- Jul 13th 2010, 09:47 AM #5

- Joined
- May 2006
- From
- Lexington, MA (USA)
- Posts
- 12,028
- Thanks
- 849

Hello, jess0517!

We can prove it by deriving that function ourselves . . .

$\displaystyle \text{Let }\{a\} \text{ be a sequence satisfying:}$

. . $\displaystyle a_1 = 1,\;\;a_2 = 8,\;\;a_n \:=\:a_{n-1} + 2a_{n-2}\:\text{ for }n \ge 3.$

$\displaystyle \text{Prove that: }\;a_n \;=\;3\!\cdot\!2^{n-1} + 2(\text{-}1)^n\:\text{ for }n \in N.$

We have: .$\displaystyle a_n - a_{n-1} - 2a_{n-2} \;=\;0$

Let $\displaystyle X^n = a_n$

. . and we have: .$\displaystyle X^n - X^{n-1} - 2X^{n-2} \:=\:0$

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

. . Then: .$\displaystyle (X - 2)(X+1) \:=\:0 \quad\Rightarrow\quad X \:=\:2,\:-1$

The generating function is of the form: .$\displaystyle f(n) \;=\;A\!\cdot\!2^n + B\!\cdot\!(\text{-}1)^n$

We know the first two values of the sequence:

. . $\displaystyle \begin{array}{cccccccccc}

f(1) = 1\!: && 2A - B &=& 1 & [1] \\

f(2) = 8\!: && 4A + B &=& 8 & [2] \end{array}$

Add [1] and [2]: .$\displaystyle 6A \:=\:9 \quad\Rightarrow\quad A \:=\:\frac{3}{2}$

Substitute into [1]: .$\displaystyle 2(\frac{3}{2}) - B \:=\:1 \quad\Rightarrow\quad B \:=\:2$

Hence: .$\displaystyle f(n) \;=\;\frac{3}{2}\!\cdot\!2^n + 2(\text{-}1)^n $

Therefore: .$\displaystyle a_n \;=\;3\!\cdot\!2^{n-1} + 2(\text{-}1)^n$

- Jul 14th 2010, 02:29 AM #6