General solution of recurrence relation if two equal roots

Question

Consider the recurrence relation $$ ax_{n+1}+bx_n+cx_{n-1}=0 $$ If the characteristic equation $$ a\lambda^2+b\lambda+c=0 $$ has two equal roots, then the general solution is given by $$ x_n=(A+nB)\alpha^n. $$

Could you please explain that to me, I do not see that!

Answer 1

First divide through by $a$ to get the form $x_{n+1}+px_n+qx_{n-1}=0$

$\lambda$ will still be a root of $\lambda^2+p\lambda+q=0$, and it will be a double root if $p=-2\lambda, q=\lambda^2$

Now let $y_n=x_n-\lambda x_{n-1}$

We have $0=x_{n+1}-2\lambda x_n + x_{n-1}=(x_{n+1}-\lambda x_n)-\lambda (x_n-\lambda x_{n-1})=y_{n+1}-\lambda y_n$

And this means $y_{n+1}=\lambda y_n =\dots = \lambda^{n+1}y_0 = B\lambda^{n+1}$

Now consider $$y_n+\lambda y_{n-1}+\lambda ^2 y_{n-2}+\dots \lambda ^{n-1}y_1=x_n-\lambda x_{n-1}+\lambda x_{n-1}-\lambda^2 x_{n-2} + \dots-\lambda^nx_0$$

The left-hand side with $n$ equal terms is just $nB\lambda^n$. The right-hand side cancels except for the first and last term to give $x_n-\lambda^nx_0=x_n-A\lambda^n$. Putting this together and rearranging gives $$x_n=(A+nB)\lambda^n$$

Answer 2

If equation has two equal roots then we can write $D=0$ or $b^2=4ac$ or $c=b^2/4a$ .Then we write $ax_{n+1}+bx_n+b^2/4a*x_{n−1}=0$ or $ax_{n+1}=-bx_n-b^2/4a*x_{n−1}$ or $x_{n+1}=-b/a(x_n+(b/4a)*x_{n−1})$.
Let $a_1=u$ and $a_2=w$ .Let $-a/b=t$ Then we get $a_3=t(x_2-1/4tx_1)=t(w-1/4*ut)$. Then we get $a_4=t(x_3-1/4*tx_2)=t^2(w-1/4*ut)-1/4*w)$ . We can show by induction that all next numbers will be shown using $t,u$ and $w$ and then we get answer

Answer 3

Consider the zeta transform of the series $\{x_n\}^{\infty}_{n=0}$ defined as $$\mathcal{Z}\{x_n\}(z)=\sum^{\infty}_{n=0}\frac{x_n}{z^n}$$ Transforming both sides of the main equation yields $$a\mathcal{Z}\{x_{n+1}\}(z)+b\mathcal{Z}\{x_n\}(z)+c\mathcal{Z}\{x_{n-1}\}(z)=0$$ Notice that $\mathcal{Z}\{x_{n+1}\}(z)=z\mathcal{Z}\{x_{n}\}(z)-zx_0$ and $\mathcal{Z}\{x_{n-1}\}(z)=z^{-1}\mathcal{Z}\{x_n\}(z)$ thus $$az\mathcal{Z}\{x_n\}(z)-zx_0+b\mathcal{Z}\{x_n\}(z)+cz^{-1}\mathcal{Z}\{x_n\}(z)=0\Rightarrow \mathcal{Z}\{x_n\}(z)=\frac{z^2x_0}{az^2+bz+c}$$ Basically this is the generating function of the original recurrence formula. Now assume the polynomial $P(z)=az^2+bz+c$ has two equal roots than $$P(z)=a(z-\alpha)^2$$ where $\alpha$ is the root of the polynomial. Then the generating function could be expressed as $$\mathcal{Z}\{x_n\}(z)=\frac{z^2x_0}{a(z-\alpha)^2}=\frac{x_0z}{a\alpha}\cdot \frac{\alpha z}{(z-\alpha)^2}$$ But on the other side one has $$\frac{\alpha z}{(z-\alpha)^2}=\sum^{\infty}_{n=0}\frac{n\alpha^n}{z^n}$$ Therefore $$\mathcal{Z}\{x_n\}(z)=\frac{x_0z}{a\alpha}\cdot\sum^{\infty}_{n=0}\frac{n\alpha^n}{z^n}$$ So one has on the left and right side respectively $$x_0+\frac{x_1}{z}+\frac{x_2}{z^2}+...=\frac{x_0z}{a\alpha}\cdot(\frac{\alpha}{z}+\frac{2\alpha^2}{z^2}+...)\Rightarrow x_0+\frac{x_1}{z}+\frac{x_2}{z^2}+...=\frac{x_0}{a}+\frac{2x_0\alpha}{az}+\frac{3x_0\alpha^2}{az^2}+...$$ Assuming $x_0\neq0$ (as otherwise the solution is trivial, the zero series) then $a=1$ and $$x_n=\frac{nx_0\alpha^{n-1}}{a}=nx_0\alpha^{n-1}$$ Notice that $$ax_{n+1}+bx_{n}+cx_{n-1}=a\frac{(n+1)x_0\alpha^{n}}{a}+b\frac{nx_0\alpha^{n-1}}{a}+c\frac{(n-1)x_0\alpha^{n-2}}{a}=\frac{x_0\alpha^{n-2}}{a}\{(n+1)a\alpha^2+bn\alpha+(n-1)c\}=\frac{x_0\alpha^{n-2}}{a}\{n(a\alpha^2+b\alpha+c)+a\alpha^2-c\}=0$$ since $\alpha$ is a root of the quadratic polynomial and $\alpha^2=c/a$ as it is a double root. So $$x_n=\frac{nx_0\alpha^{n-1}}{a}=nx_0\alpha^{n-1}$$ is a solution. Also on the other side since $\alpha$ is a root of the quadratic polynomial then $x_n=c_0\alpha^n$ for some constant $c_0$ is a solution to the recurrence formula (easy to check). Therefore the general solution is the linear combination below: $$x_n=c_0\alpha^n+nx_0\alpha^{n-1}=(c_0+\frac{x_0}{\alpha}n)\alpha^n$$ Set $A=c_0$ and $B=\frac{x_0}{\alpha}$ and you are done. $$$$

Answer 4

Let $D$ be defined as $(Dx)_n = x_{n+1}$. Assuming $a \neq 0$, we have $x_{n+2}+{b \over a} x_{n+1} + {c \over a}x_n = 0$, or $(D^2 +{b \over a} D + {c \over a}I)x = 0$. Suppose $\lambda$ is the repeated root of the quadratic $y^2+{b \over a} y + {c \over a} = 0$, then we can write the difference equation as $(D-\lambda)^2 x = 0$.

We see that $(D-\lambda) x = 0$ iff $x_n = x_0 \lambda^n$ for some $x_0$ (with the convention that $0^n = \delta_{0n}$).

Also note that if $c$ is a constant, then $(D-1)x = c$ iff $x_n = x_0 +nc$ for some $x_0$.

We can write the equation $(D-\lambda)^2 x = 0$ as the pair of equations $(D-\lambda)y = 0$, $(D-\lambda) x = y$.

The first gives $y_n = y_0 \lambda^n$ for some $y_0$.

If $\lambda = 0$, then solving $(D x)_n = y_0 \delta_{0n}$ gives $x_n = x_0 \delta_{0 n}+ y_0 \delta_{1 n}$ for some $x_0,y_0$ (that is, the sequence $x=(x_0,y_0,0,...)$).

If $\lambda \neq 0$, then we have ${1 \over \lambda^n}((D-\lambda)x)_n = y_0$. Let $l$ denote the function $l_n = \lambda^n$, then we have ${ 1\over l} (D-\lambda) x = y_0$. Expanding gives ${1 \over l} Dx - {1 \over l} \lambda x = \lambda D {x \over l} - \lambda {x \over l} = \lambda (D-1) {x \over l} = y_0$, or $(D-1) {x \over l} = { y_0 \over \lambda}$.

Noting that $n \mapsto { y_0 \over \lambda}$ is a constant function, we see that this gives $({x \over l})_n = {x_n \over \lambda^n} = x_0 + n {y_0 \over \lambda}$, or $x_n = (x_0 + n {y_0 \over \lambda}) \lambda^n$, which is the desired form.