0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry, but $a(k-1)$ is not the same as $a * (k-1)$. So $a_2$ is $4a_1 -2a_0$ and is not a $4a$. $\endgroup$ – Evgeny May 7 '15 at 7:12
  • $\begingroup$ Now it makes way more sense, the way he posted the question is very confusing and symbolically incorrect $\endgroup$ – alkabary May 7 '15 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.