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

In summary: As desired.In summary, we found a generating function for the given linear homogeneous recurrence, and then used the theorem for partial fraction decomposition to obtain a formula for the $n$th term in terms of the characteristic roots.
  • #1
Nono713
Gold Member
MHB
618
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
  • #2
The characteristic roots are:

\(\displaystyle r=-1\pm\sqrt{3}\)

and so the closed form is:

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

Using the given initial values, we may write:

\(\displaystyle a_0=k_1+k_2=2\)

\(\displaystyle 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:

\(\displaystyle k_1=k_2=1\)

and so the closed form is:

\(\displaystyle a_n=(-1+\sqrt{3})^n+(-1-\sqrt{3})^n\)
 
  • #3
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)
 
  • #4
The associated auxiliary equation is:

\(\displaystyle r^2+2r-2=0\)

Use of the quadratic equation gives the characteristic roots.

We essentially assume a solution of the form:

\(\displaystyle a_n=r^n\) where \(\displaystyle r\ne0\)

and so substitution into the recursion gives:

\(\displaystyle r^n=-2r^{n-1}+2r^{n-2}\)

Dividing through by \(\displaystyle r^{n-2}\) and rearranging in standard quadratic form gives the characteristic or auxiliary equation above.
 
  • #5
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$$
 

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

What is a recurrence challenge?

A recurrence challenge is a problem or situation that reoccurs or repeats itself over time. It can also refer to a scientific or mathematical concept where patterns or sequences repeat in a predictable manner.

Why is understanding recurrence challenges important in science?

Understanding recurrence challenges is important in science because it allows us to identify patterns and make predictions based on those patterns. This can help us understand natural phenomena, develop theories, and make advancements in various fields of research.

What are some examples of recurrence challenges in science?

Some examples of recurrence challenges in science include the cyclical patterns of the seasons, the repeated phases of the moon, and the predictable behavior of chemical reactions. In mathematics, recurrence challenges can be seen in the Fibonacci sequence and the Mandelbrot set.

How do scientists approach solving recurrence challenges?

Scientists approach solving recurrence challenges by analyzing data and looking for patterns. They may also use mathematical models and simulations to understand the underlying mechanisms behind the recurrence. Additionally, scientists may conduct experiments and gather more data to test their hypotheses.

What are some potential applications of understanding recurrence challenges?

Understanding recurrence challenges has a wide range of potential applications in science. It can help us predict natural disasters, control the spread of diseases, and develop more efficient technologies. It can also aid in understanding complex systems and making more accurate forecasts in fields such as economics and climate science.

Similar threads

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