MHB Non-recursive formula for the $n$th term of a linear homogeneous recurrence

Nono713
Gold Member
MHB
Messages
615
Reaction score
4
Just an easy one to start off with, find a non-recursive formula for the $n$th term of the following linear homogeneous recurrence:

$$a_0 = 2, ~ ~ a_1 = -2, ~ ~ a_n = -2 a_{n - 1} + 2 a_{n - 2} ~ ~ \text{for} ~ n \geq 2$$​

Hint:
You can use generating functions to solve this problem.
 
Mathematics news on Phys.org
The characteristic roots are:

$$r=-1\pm\sqrt{3}$$

and so the closed form is:

$$a_n=k_1(-1+\sqrt{3})^n+k_2(-1-\sqrt{3})^n$$

Using the given initial values, we may write:

$$a_0=k_1+k_2=2$$

$$a_1=k_1(-1+\sqrt{3})+k_2(-1-\sqrt{3})=-(k_1+k_2)+\sqrt{3}(k_1-k_2)=-2+\sqrt{3}(k_1-k_2)=-2$$

Thus:

$$k_1=k_2=1$$

and so the closed form is:

$$a_n=(-1+\sqrt{3})^n+(-1-\sqrt{3})^n$$
 
But how did you work out those characteristic roots? Show your working :cool:

(I don't actually know what characteristic roots are - are they that easy to derive? I approached this with generating functions myself)
 
The associated auxiliary equation is:

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

Use of the quadratic equation gives the characteristic roots.

We essentially assume a solution of the form:

$$a_n=r^n$$ where $$r\ne0$$

and so substitution into the recursion gives:

$$r^n=-2r^{n-1}+2r^{n-2}$$

Dividing through by $$r^{n-2}$$ and rearranging in standard quadratic form gives the characteristic or auxiliary equation above.
 
Let $a(z) = \sum_{i = 0}^\infty a_i z^i = a_0 + a_1 z + a_2 z^2 + \cdots$ be a generating function such that $a_n$ corresponds to said recurrence. Consider:

$$a(z) + 2 z a(z) - 2 z^2 a(z)$$
The reason we do this is because when we multiply $a(z)$ by $z$, we increment every exponent in the generating function by $1$, and then $a_1$ is paired with $z^2$, $a_2$ is paired with $z^3$, and so on. So we see that the sum above is just the recurrence relation, encoded into a sum of generating functions. Let's write down the first few terms of these three different generating functions:

$$
\begin{array}{|c|cccl|}
\hline
a(z) &a_0 &a_1 z &a_2 z^2 &\cdots \\
2 z a(z) &~ &2 a_0 z &2 a_1 z^2 &\cdots \\
-2 z^2 a(z) &~ &~ &- 2 a_0 z^2 &\cdots \\
\hline
\text{Sum} &a_0 &(a_1 + 2a_0) z &0 &\cdots \\
\hline
\end{array}
$$
We note the resulting coefficients for $z^2, z^3, \cdots$ are zero, since $a_n = -2 a_{n - 1} + 2 a_{n - 2}$ for $n \geq 2$. It follows that:

$$a(z) + 2 z a(z) - 2 z^2 a(z) = a_0 + (a_1 + 2 a_0) z$$
Rearranging, we obtain:

$$a(z) \left ( 1 + 2 z - 2 z^2 \right ) = a_0 + (a_1 + 2 a_0) z$$
Now we may plug in the initial values $a_0 = 2$, $a_1 = -2$ into the equation:

$$a(z) \left ( 1 + 2 z - 2 z^2 \right ) = 2 + 2 z$$
To finally obtain an expression for $a(z)$, our original generating function:

$$a(z) = \frac{2 + 2z}{1 + 2 z - 2 z^2}$$
By partial fraction decomposition, we can deduce that:

$$a(z) = \frac{\alpha}{\alpha + 2z} + \frac{\beta}{\beta - 2z} = \frac{1}{1 + \frac{2}{\alpha} z} + \frac{1}{1 - \frac{2}{\beta} z}$$
Where $\alpha = \sqrt{3} - 1$ and $\beta = \sqrt{3} + 1$. We can then use the theorem that:

$$\frac{1}{1 - nz} = \sum_{i = 0}^\infty n^i z^i$$
This yields:

$$a(z) = \sum_{i = 0}^\infty \left ( - \frac{2}{\alpha} \right )^i z^i + \sum_{i = 0}^\infty \left ( \frac{2}{\beta} \right )^i z^i = \sum_{i = 0}^\infty \left [ \left ( - \frac{2}{\alpha} \right )^i + \left ( \frac{2}{\beta} \right )^i \right ] z^i$$
And we can then just read off the coefficient of $z^i$ to evaluate the recurrence at $a_i$. We conclude:

$$a_n = \left ( - \frac{2}{\alpha} \right )^n + \left ( \frac{2}{\beta} \right )^n = \left ( - \frac{2}{\sqrt{3} - 1} \right )^n + \left ( \frac{2}{\sqrt{3} + 1} \right )^n$$
Which, after simplifying the fractions, becomes:

$$a_n = \left ( - \sqrt{3} - 1 \right )^n + \left ( \sqrt{3} - 1 \right )^n$$
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
I'm interested to know whether the equation $$1 = 2 - \frac{1}{2 - \frac{1}{2 - \cdots}}$$ is true or not. It can be shown easily that if the continued fraction converges, it cannot converge to anything else than 1. It seems that if the continued fraction converges, the convergence is very slow. The apparent slowness of the convergence makes it difficult to estimate the presence of true convergence numerically. At the moment I don't know whether this converges or not.

Similar threads

Replies
4
Views
3K
Replies
11
Views
2K
Replies
11
Views
2K
Replies
6
Views
2K
Replies
2
Views
1K
Back
Top