Recursive sequence calculation

Question

So I have a finite sequence with K+1 terms .I'm trying to rewrite the following recursive sequence as a general term:

$ a_{n+1} = 2a_n -a_{n-1} $

given $ a_0 = 1 , a_K =0$

Would love to know if there is a simple solution to this problem?

Cheers

Answer 1

First, as J. W. Tanner has pointed out, we have that $a_{n+1}-a_n=a_n-a_{n-1}$, (presumably for $1\le n\le K-1$).

Let's let $d=a_1-a_0$.

Note that we can sum the following telescoping series to get:

$$\sum_{i=1}^{K}(a_n-a_{n-1})=a_K-a_0=0-1=-1.$$

But also note that each term in this series is equal to $d$. Hence we have that $Kd=-1$. So $d=-\frac{1}{K}$. And it follows that $a_n=1-\frac{n}{K}$ for all $0\le n\le K$.

Answer 2

Hint:

It's $a_{n+1}-a_n=a_n-a_{n-1}=\dots=a_1-a_0$,

so can you show by induction that $a_n=n(a_1-a_0)+a_0$ and take it from there?

Answer 3

Such recurrence relations are solved by finding a solution of the form $a_n=r^n$, and by plugging this expression in the equation, we obtain

$$(r^2-2r+1)r^{n-1}=(r-1)^2r^{n-1}=0.$$

This is made true with $r=1$, so that a solution is just

$$a_n=1.$$

But this root is double and theory tells us that another solution of the form $a_n=an$ exists. Indeed

$$a(n+1)=2an-a(n-1)$$ works for any $a$.

Hence the general solution

$$a_n=an+1,$$ which must be such that

$$a_k=ak+1=0,$$ giving you $a$.

---

Note that Tanner's hint leads to the solution in a simpler way.

Answer 4

Note that, $$a_{n+1} = 2a_n - a_{n-1}$$ and $$a_n = a_n$$ can be rewritten as $$\begin{bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a_{n} \\ a_{n-1}\end{bmatrix}.$$

We can diagonalize $$\begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix} = SJS^{-1}$$ where $$ J = \begin{bmatrix} 1-\sqrt{2} & 0 \\ 0 & 1+\sqrt{2} \end{bmatrix}.$$ I am leaving $S$ as exercise.

Now, $$\begin{bmatrix} a_{n+1} \\ a_n\end{bmatrix} = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} a_{n} \\ a_{n-1}\end{bmatrix} =\begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}^2\begin{bmatrix} a_{n-1} \\ a_{n-2}\end{bmatrix}=\cdots = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}^n\begin{bmatrix} a_{1} \\ a_{0}\end{bmatrix} = SJ^nS^{-1}\begin{bmatrix} a_{1} \\ a_{0}\end{bmatrix}$$.

From this, you can figure out the solution.

However, you are the second person in a month, trying to solve the finite difference approximation of Laplace problem using recursive relations. Why do you want to do that?