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

AI Thread Summary
The discussion focuses on deriving a non-recursive formula for the nth term of a linear homogeneous recurrence defined by specific initial conditions and a recurrence relation. The approach utilizes generating functions to encode the recurrence into a sum, leading to the formulation of the generating function a(z). By substituting the initial values into the derived equation, the generating function is expressed as a rational function. Through partial fraction decomposition and application of a series expansion theorem, the nth term is ultimately expressed as a combination of powers involving characteristic roots. The final formula for the nth term is a_n = (-√3 - 1)^n + (√3 - 1)^n.
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$$
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Thread 'Imaginary Pythagorus'
I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...

Similar threads

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