1
$\begingroup$

Given a sequence $\{x_n\}$ where $x_n = 2x_{n-1} + 3x_{n-2}$ how can one express it in terms of ${x_0, x_1, n}$. Can this be generalized for ${x_n = \alpha x_{n-1} + \beta x_{n-2}}$

I've tried to use the following approach: $$\eqalign{ & 1x_0 = x_01 \\ & zx_1 = x_1z \\ & z^2x_2 = (2x_1 + 3x_0)z^2 \\ & z^3x_3 = (2x_2 + 3x_1)z^3 \\ & z^4x_4 = (2x_3 + 3x_2)z^4 \\ & ... \\ & z^nx_n = (2x_{n-1} + 3x_{n-2})z^n }$$

Then sum LHS with RHS which will produce:

$${ x_0 + \sum\limits_{k = 1 }^na_nz^n = x_0 +zx_1 + 2\sum\limits_{k = 2}^nx_{n-1}z^n + 3 \sum\limits_{k = 2}^n x_{n-2}z^n }$$

Let $${ G(z) = x_0 + \sum\limits_{k = 1 }^na_nz^n }$$

Then RHS may be expressed in terms of ${G(z)}$. For example $${ 2\sum\limits_{k = 2}^na_{n-1}z^n = 2z\sum\limits_{k = 2}^na_{n-1}z^{n-1} = 2z(\sum\limits_{k = 1}^na_{n}z^{n} + x_0 - x_0) = 2z(G(z) - x_0) }$$

Applying those transformations I eventually got ${G(z)}$ expressed in terms of z and ${x_1, x_0}$. But at this point I got stuck.

I got a sum of fractions: $${ \frac{3x_0 - x_1}{4(1+z)}+\frac{x_0+x_1}{4(1-3z)} }$$

I guess i could expand the fractions into series and find their sum, but i am not supposed to know about such expansions at the point of the book i took the problem from.

All of the above feels like a wrong approach. So the question is whether this can be done in a more elegant way.

$\endgroup$
  • $\begingroup$ Would you be allowed to use Taylor series? $\endgroup$ – Alex D May 2 '18 at 20:01
  • $\begingroup$ @AlexD Unfortunately no, according to the positions in the book I should not yet "know" about Taylor series and even derivatives. Your idea makes sense, but the author expects this to be solved without using series expansions $\endgroup$ – roman May 3 '18 at 9:01
6
$\begingroup$

Solving recurrence relations is actually very similar to solving ODEs. For simplicity, lets stick with the general second order recurrence relation

$$a_n=\alpha a_{n-1}+\beta a_{n-2}$$

Firstly, observe that if $a_n=f(x_0,x_1,n)$ and $a_n=g(x_0,x_1,n)$ are both solutions, then $a_n=(f+g)(x_0,x_1,n)$ is also a solution.

Now, we guess the solution $a_n=\lambda^n$ for some constant $\lambda$ to be determined. Plugging this in:

\begin{align} \ & a_n=\alpha a_{n-1}+\beta a_{n-2} \\ \ \implies & \lambda^n=\alpha \lambda^{n-1}+\beta \lambda^{n-2} \\ \ \implies & \lambda^2-\alpha\lambda-\beta=0 \end{align}

i.e. $\lambda$ is a root to this quadratic. Let the two roots of this quadratic be $\lambda_1$ and $\lambda_2$. Then the general solution would be

$$a_n=A\lambda_1^n+B\lambda_2^n$$

where the constants $A$ and $B$ are to be determined by the initial conditions. As per your question with the general case, if $a_0=a_0$ and $a_1=a_1$, then we have

$$a_0=a_0 \implies a_0=A+B$$

$$a_1=a_1 \implies a_1=A\lambda_1+B\lambda_2$$

and we solve for $A$ and $B$ from here.


In your example where you had the recurrence relation

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

By guessing the solution $a_n=\lambda^n$, we arrive at the quadratic

$$\lambda^2-2\lambda-3=0$$

giving the roots $\lambda_1=3$ and $\lambda_2=-1$. Thus, the general solution is

$$a_n=A\cdot 3^n+B\cdot (-1)^n$$

Plugging in $n=0$ and $n=1$, we get

$$a_0=A+B \qquad a_1=3A-B$$

Hence $A=\frac{a_0+a_1}{4}$ and $B=\frac{3a_0-a_1}{4}$, giving

$$a_n=\frac{a_0+a_1}{4}\cdot 3^n+\frac{3a_0-a_1}{4}\cdot (-1)^n$$

$\endgroup$
  • $\begingroup$ wow, this is beautiful, thank you for your answer. I'm just wondering why the fact that ${a_n = f(x_0, x_1, n)}$ and ${a_n = g(x_0, x_1, n)}$ implies that ${a_n = (f + g)(x_0, x_1, n)}$. $\endgroup$ – roman May 3 '18 at 9:04
  • $\begingroup$ @RomanKapitonov This is a consequence of the superposition principle. See the link en.wikipedia.org/wiki/Superposition_principle $\endgroup$ – Alex D May 3 '18 at 9:15
2
$\begingroup$

Consider the matrix:

$$ X_n = \begin{bmatrix} x_{n+2} & x_{n+1} \\ x_{n+1} & x_{n} \end{bmatrix} $$

Then there is a recurrence relation:

$$X_{n+1} = X_n \begin{bmatrix} 2 & 1 \\ 3 & 0 \end{bmatrix} $$

So we may say that

$$X_{n} = X_0 \begin{bmatrix} 2 & 1 \\ 3 & 0 \end{bmatrix}^{n} = X_0A^n$$

Through whatever method you'd like to use, realize the eigenvectors of $A$ are $(-1, 3)$ and $(1, 1)$, with values $-1$ and $3$. Thus through a change of basis,

$$A = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & 3 \end{bmatrix} \begin{bmatrix} -1/4 & 1/4 \\ 3/4 & 1/4 \end{bmatrix} $$ and $$ A^n = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} -1 & 0 \\ 0 & 3 \end{bmatrix}^n \begin{bmatrix} -1/4 & 1/4 \\ 3/4 & 1/4 \end{bmatrix} = \begin{bmatrix} -1 & 1 \\ 3 & 1 \end{bmatrix} \begin{bmatrix} (-1)^n & 0 \\ 0 & 3^n \end{bmatrix} \begin{bmatrix} -1/4 & 1/4 \\ 3/4 & 1/4 \end{bmatrix} $$ Finally, let $x_0 = 0$ (or whatever, it don't matter) so that $$ X_0= \begin{bmatrix} x_2 & x_1 \\ x_1 & x_0 \end{bmatrix}$$ Then multiplying, (the top-right and bottom-left elements are actually equal) $$ X_n= \begin{bmatrix} \dfrac{3^{n+1}(x_2 + x_1) - (-1)^{n}(3x_1 - x_2)}{4} & \dfrac{3^{n}(x_2 + x_1) + (-1)^{n}(3x_1 - x_2)}{4} \\ \dfrac{3^{n+1}(x_1 + x_0) - (-1)^{n}(3x_0 - x_1)}{4} & \dfrac{3^{n}(x_1 + x_0) + (-1)^{n}(3x_0 - x_1)}{4} \end{bmatrix} $$ The bottom right element is $x_n$. Thus, $$x_n = \frac{3^{n}(x_1 + x_0) + (-1)^{n}(3x_0 - x_1)}{4}$$

$\endgroup$
  • $\begingroup$ Thank you for guiding through a different approach using matrices. Never thought the problem may be solved your way. $\endgroup$ – roman May 3 '18 at 9:11
  • $\begingroup$ Yes, in this manner one doesn't need to "guess" for a solution. $\endgroup$ – Jeffery Opoku-Mensah May 3 '18 at 20:24
2
$\begingroup$

Let $f(x)$ be the generating function for some sequence $(a_{n})_{n\in\mathbb{N}}$ such that \begin{align*} f(x)=\frac{c}{bx+d}=\sum^{\infty}_{n=0}{a_{n}x^{n}},\ c,b,d\in\mathbb{Z}.\tag{1} \end{align*} Then \begin{alignat*}{3} f(x)=\frac{c}{bx+d}&\implies f^{\prime}(x) &&=-1!\left(\frac{b}{c}\right)^{1}f(x)^{2}\\ &\implies f^{\prime\prime}(x) &&=+2!\left(\frac{b}{c}\right)^{2}f(x)^{3}\\ &\implies f^{\prime\prime\prime}(x) &&=-3!\left(\frac{b}{c}\right)^{3}f(x)^{4}\\ &\qquad &&\vdots\\ &\implies f^{n}(x) &&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}\big(f(x)\big)^{n+1}, \end{alignat*}

where $f^{n}(x)$ denotes the $n^{\text{th}}$ derivative of $f$ with respect to $x.$ If we evaluate $f^{n}(0)$, the Maclaurin series expansion of $f(x)$ is then given by

\begin{alignat*}{4} &\qquad \qquad \qquad \qquad \quad f^{n}(0)&&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}f(0)^{n+1}\\ & &&=(-1)^{n}n!\left(\frac{b}{c}\right)^{n}\left(\frac{c}{d}\right)^{n+1}\\ &\qquad \qquad \qquad \quad \implies f(x) &&=\sum_{n=0}^{\infty }c\ (-1)^{n}\left(\frac{1}{d}\right)^{n+1}{b^{n}x^{n}}.\tag{2}\\ \end{alignat*} It follows from (1) and (2) that the explicit form of the sequence $(a_{n})_{n\in\mathbb{N}}$ is given by \begin{align*}a_{n}=c\ (-1)^{n}\left(\frac{1}{d}\right)^{n+1} b^{n}.\tag{3}\\ \end{align*}
If we let $c=x_{0}+x_{1},\ b=-12,$ and $d=4$, as in (1) then

\begin{alignat*}{3} g(x)=\frac{x_{0}+x_{1}}{4-12z}&\overset{(3)}{\implies} g_{n}&&=(-1)^{n}(x_{0}+x_{1})(-12)^{n}\left(\frac{1}{4}\right)^{n+1}\\ &\qquad &&=(x_{0}+x_{1})(-1)^{n}(-1)^{n}(3)^{n}(4)^{n}\left(\frac{1}{4}\right)^{n}\left(\frac{1}{4}\right)\\ &\ \implies g_{n} &&=\left(\frac{1}{4}\right)3^{n}(x_{0}+x_{1}).\tag{4} \end{alignat*} Similarly \begin{alignat*}{3} h(x)=\frac{3x_{0}-x_{1}}{4+4z}&\overset{3}{\implies} h_{n}&&=(-1)^{n}(3x_{0}-x_{1})(4)^{n}\left(\frac{1}{4}\right)^{n+1}\\ &\qquad &&=(3x_{0}-x_{1})(-1)^{n}(4)^{n}\left(\frac{1}{4}\right)^{n}\left(\frac{1}{4}\right)\\ &\ \implies h_{n} &&=(-1)^{n}\left(\frac{1}{4}\right)(3x_{0}-x_{1}).\tag{5}\\ \end{alignat*} It follows from the linearity of differentiation, (superposition principle), that we may combine (4) and (5) to obtain the desired formula for $x_{n}$. Whence,

\begin{align}x_{n}=\left(\frac{1}{4}\right)3^{n}(x_{0}+x_{1})+ (-1)^{n}\left(\frac{1}{4}\right)(3x_{0}-x_{1})\tag*{$\square$}\end{align}

$\endgroup$
  • $\begingroup$ Does this match with the form given by the other posters? Isn't $a_n$ the sum of two such series? $\endgroup$ – Jeffery Opoku-Mensah May 3 '18 at 1:27
  • $\begingroup$ @JefferyOpoku-Mensah Sure, I've updated the answer. $\endgroup$ – Alex D May 3 '18 at 3:33
  • $\begingroup$ @AlexD I was also thinking of this approach but as per the OP I'm not supposed to use series expansions. Thank you for your answer the above absolutely makes sense. $\endgroup$ – roman May 3 '18 at 9:07
0
$\begingroup$

Use generating functions. Define $g(z) = \sum_{n \ge 0} x_n z^n$, take the recurrence shifted by 2, multiply by $z^n$ and sum over $n \ge 0$, recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} x_{n + 2} z^n &= 2 \sum_{n \ge 0} x_{n + 1} z^n + 3 \sum_{n \ge 0} x_n z^n \\ \frac{g(z) - x_0 - x_1 z}{z^2} &= 2 \frac{g(z) - x_0}{z} + 3 g(z) \end{align*}$

Solve for $g(z)$, write as partial fractions; extract coefficient of $z^n$:

$\begin{align*} g(z) &= \frac{x_0 + (x_1 - 2 x_0) z}{1 - 2 z - 3 z^2} \\ &= \frac{x_0 + x_1}{4 (1 - 3 z)} + \frac{3 x_0 - x_1}{4 (1 + z)} \\ x_n &= [z^n] g(z) \\ &= \frac{x_0 + x_1}{4} \cdot 3^n + \frac{3 x_0 - x_1}{4} \cdot (-1)^n \end{align*}$

The last because the series is:

$\begin{align*} \sum_{n \ge 0} a^n z^n &= \frac{1}{1 - a z} \end{align*}$

$\endgroup$

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.