nth term of recurrence

Question

Im Trying to find/learn how to get the general formula for the n'th term. Im new to algebra and recurrences

$$a_k = \left\{ \begin{array}{lr} 4a_{k-1} - 2a_{k-2} &: if \space k \geq 2 \\ 2 & :if\space k =1 \\ 1 & :if \space k =0 \end{array} \right.$$

Can anybody explain this general formula. I would like to get my head around it and try and understand.

Answer 1

Lets list the first few numbers in that sequence.

when $k=0$ we do have $a_0 = 1$

When $k=1$ we do have $a_1 = 2$

Now for $k=2$ we have $a_2 = 4a_{2-1} - 2a_{2-2} = 4a_1 -2a_0 =4(2) -2(1) = 6$

for $k=3$ we have $a_3 = 4a_{3-1} -2a_{3-2} = 4a_2 -2a_1 = 4(6) -2(2) = 20$

for $k =4$ we have $a_4 = 4a_{4-1} -2a_{4-2} = 4a_3 -2a_2 =4(20) - 2(6) =68$

and so the sequence is like $$1,2,6,20,68,......$$

Notice that this sequence is a monotone increasing sequence ($a_{k+1} \geq a_k \space \forall \space k \geq 0$)

Answer 2

Hint

Let me suppose that what you posted is $$a_{k}=4a_{k-1}-2a_{k-2}$$ which is a recurrence relation.

As usual, we write the corresponding characteristic equation which, here, is $$r^2=4r-2$$ the roots of which being $r_{\pm}=2\pm\sqrt 2$. So the general form of the recurrence relation is $$a_k=c_1(2+\sqrt 2)^k+c_2(2-\sqrt 2)^k$$ Now apply the conditions to get the values of $c_1$ and $c_2$.

Using the binomial theorem should remove all radicals from the expression.

Is this what you were looking for ?

Answer 3

Forming the characteristic equation, we have: $$ r^2 - 4r + 2 = 0 $$ Using the quadratic formula, we obtain two distinct real roots: $$ r = 2 \pm \sqrt 2 $$ Hence, for some scalars $A$ and $B$, the general formula has the form: $$ a(k) = A(2 + \sqrt 2)^k + B(2 - \sqrt 2)^k $$ By plugging in the initial conditions, we obtain the following system of equations: $$ \begin{cases} 1 = a(0) = A + B \\ 2 = a(1) = (2 + \sqrt 2)A + (2 - \sqrt 2)B \end{cases} $$ Solving, we obtain $A = B = 1/2$. Hence, we conclude that: $$ a(k) = \frac{1}{2}(2 + \sqrt 2)^k + \frac{1}{2}(2 - \sqrt 2)^k $$

Answer 4

Without getting into the theory, one can often solve recurrences by assuming that the series tends asymptotically to a geometric series (without quite reaching one). There will generally be two or more geometric series that satisfy the recurrence, and a linear combination of them will yield the desired series.

For instance, suppose we try to make the $a_2$ and later terms conform to a geometric series, so that $a_n = a_0r^n$. We would find

$$ a_n = 4a_{n-1}-2a_{n-2} $$ $$ a_0r^n = 4a_0r^{n-1}-2a_0r^{n-2} $$

and then dividing by $a_0r^{n-2}$ gives us

$$ r^2 = 4r-2 $$ $$ r^2-4r+2 = 0 $$

which can be solved using the quadratic formula to yield

$$ r_{1, 2} = \frac{4 \pm \sqrt{16-8}}{2} = 2 \pm \sqrt{2} $$

That is to say, two families of geometric series satisfy the recurrence, one being $a'_n = a'_0 (2+\sqrt{2})^n$ (for any $a'_0$), and one being $a''_n = a''_0 (2-\sqrt{2})^n$ (again for any $a''_0$). To find out which linear combination yields the desired series, we write

$$ a'_0 + a''_0 = a_0 = 1 $$ $$ a'_1 + a''_1 = a'_0(2+\sqrt{2}) + a''_0(2-\sqrt{2}) = a_1 = 2 $$

which yields the rather convenient solution $a'_0 = a''_0 = 1/2$. So our final closed-form solution is

$$ a_n = \frac{(2+\sqrt{2})^n+(2-\sqrt{2})^n}{2} $$

and you should be able to verify that the recurrence is satisfied with the initial conditions.