3

What is the general solution to the linear difference equation: $$y_{n+3}-4y_{n+2}+5y_{n+1}-2y_n=2^n$$

I followed the instructions given in this video. And I got the following for the homogeneous part I got: $$y_n^c = A+Bn+C2^n$$

for the particular part I got $$y_n^p = C_02^n$$ , putting this in the initial equation I got $C_0*0=1$, so no solution. What should I do now? Or did I do something wrong somewhere?

RobPratt
  • 45,619
Yahya Fati
  • 83
  • 2
    Hint: the characteristic equation is $(m-1)^2(m-2)$. Since it has $2$ as a root, you must replace $C_0$ with a polynomial in $m$ of sufficient degree. Work out $u_{n+3}-4u_{n+2}+5u_{n+1}-2u_n$ for $u_n=n2^n,,u_n=n^22^n$ etc. – J.G. Jun 11 '22 at 17:52
  • @J.G. Thank you very much. Why do we do that, when $m$ is $2$? I'm guessing it's because it's the base of $2^n$. What should we do in general when this happens? – Yahya Fati Jun 11 '22 at 18:06
  • I think the rule of thumb is if $m=m_0$ is a root one solution is $p(n)m_0^n$, with $p$ a polynomial whose degree is the maximum of ($m$'s multiplicity as a root minus $1$) and (one more than the degree of a polynomial multiplying $m_0^n$ on the RHS, or $0$ if there is no such term). This can be justified in terms of the affine space of solutions of an inhomogeneous difference equation, and the number of degrees of freedom of a polynomial. – J.G. Jun 11 '22 at 18:11
  • (In the example at hand, $m_0=1$ is a multiplicity-$2$ root, but as there's no $1^n$ term on the RHS we get a degree-$1$ multiple of $1^n$, which is your $A+Bn$.) – J.G. Jun 11 '22 at 18:12
  • The homogenous solution contains terms of the form $1,n,2^n$ because of the roots of characteristic equation. Note that the term $(D-2)$ annihilates $2^n$ and since the equation is $(D-1)^2 (D-2)$ we see that any solution of this equation satisfies the homogenous equation $(D-1)^2 (D-2)^2 = 0$. – copper.hat Jun 11 '22 at 19:28
  • However, not all solutions of the bigger equation are solutions of the original, so we must find a particular solution by choosing coefficients for the terms $1,n,2^n, n 2^n$. However, in this case it is a little simpler because we know the general solution contains the terms $1,n,2^n$ so we need only determine the coefficient of $n2^n$ and add that to the homogenous solution. So, to find a particular solution, try a term of the form $Cn2^n$ and determine $C$. – copper.hat Jun 11 '22 at 19:29
  • @copper.hat Thank you. This is very helpful. Could you recommend me a resource to understand this topic? Most of it looked similar to finding the particular solution in linear differential equations, which I took the previous semester but we never worked with exponential functions. So could you recommend me a resource or at least what to even search for on Google? :) – Yahya Fati Jun 11 '22 at 19:42
  • 1
    @YahyaFati Unfortunately I no longer have my old texts so have no suitable reference, but you could try searching for the terms "differential equation annihilator"? – copper.hat Jun 11 '22 at 19:57
  • What are the initial values $y_0,y_1,y_2$? – clathratus Jun 11 '22 at 21:59
  • 1
    @clathratus It would hardly be a general solution if there were initial values. – copper.hat Jun 11 '22 at 22:40

3 Answers3

3

The recurrence can be reduced to a homogeneous recurrence one degree higher by eliminating the $\,2^n\,$ power on the RHS between two consecutive relations.

$$ \begin{align} y_{n+3}-4y_{n+2}+5y_{n+1}-2y_n &= 2^n \tag{1} \\ y_{n+4}-4y_{n+3}+5y_{n+2}-2y_{n+1} &= 2^{n+1} \tag{2} \end{align} $$

Then $\,(2) - (1) \times 2\,$ gives:

$$ y_{n+4} - 6 y_{n+3} + 13 y_{n+2} - 12 y_{n+1} + 4 y_n = 0 $$

The characteristic polynomial of the latter is $\,(t-1)^2(t-2)^2\,$, so the general solution is:

$$ y_n = a + bn + (c + dn)\, 2^n $$

The initial values $\,y_0$, $y_1$, $y_2$, $y_3 = 4y_2 - 5y_1 + 2 y_0 + 1\,$ determine the constants $\,a,b,c,d\,$.

[ EDIT ] $\;$ To elaborate on the last line, the constants $\,a,b,c,d\,$ are not independent, because they are constrained by the condition that $\,y_0$, $y_1$, $y_2$, $y_3\,$ must satisfy the original recurrence:

$$ \begin{align} y_3 = a+3b + 8(c+3d) &= 4y_2 - 5y_1 + 2 y_0 + 1 \\ &= 4\left(a + 2b + 4(c+2d)\right) - 5\left(a + b + 2(c+d)\right) + 2\left(a + c\right) + 1 \\ &= a + 3 b + 8 c + 22 d + 1 \end{align} $$

Equating the first and last lines, it follows that $\,d=\dfrac{1}{2}\,$, so in the end the general solution is:

$$ y_n \;=\; a + bn + \left(c + \frac{n}{2}\right)\, 2^{n} \;=\; a + bn + \left(c' + n\right)\, 2^{n-1} $$

dxiv
  • 76,497
2

The characteristic polynomial is

$ m^3 - 4 m^2 + 5 m - 2 = (m-1)^2 (m-2) $

And the annihilator of the driving term is $(m-2)$, hence

$ (m-1)^2 (m-2)^2 (y) = 0 $

The general solution is

$ y_n = A + B n + C (2)^n + D n (2)^n $

The particular solution is $ y_p = D n (2)^n $

Plug this in the original difference equation,

$ D (n+3) 2^{n+3} - 4 D (n+2) 2^{n+2} + 5 D (n+1) 2^{n+1} - 2 D n (2)^n = 2^n $

From which it follows that

$ D ( 8 n + 24 - 16 n - 32 + 10 n + 10 - 2 n ) = 1 $

$ D = \dfrac{1}{2} $

So a particular solution is $ y_p = \dfrac{1}{2} n (2)^n $

Now the general solution is the sum of a particular solution and the homogenous solution

$y_n= y_p + y_h = \dfrac{1}{2} n (2)^n + A + B n + C (2)^n$

The constants $A,B,C$ can be determined in a straight forward manner using the initial conditions $y_0, y_1, y_2 $ or $ y_1, y_2, y_3 $, by building a $3 \times 3 $ linear system in $A, B,C$ which can be solved using Gauss-Jordan elimination. Explicity, we have

$ \begin{bmatrix} 1 && 1 && 2 \\ 1 && 2 && 4 \\ 1 && 3 && 8 \end{bmatrix} \begin{bmatrix} A \\ B \\ C \end{bmatrix} = \begin{bmatrix} y_1 - 1 \\ y_2 - 4 \\ y_3 - 12 \end{bmatrix} $

Hosam Hajeer
  • 21,978
1

Let $$f(x)=\sum_{n\ge0}y_nx^n.$$ Then multiply the recurrence by $x^{n+3}$ and sum over $n\ge0$: $$\sum_{n\ge0}y_{n+3}x^{n+3}-4x\sum_{n\ge0}y_{n+2}x^{n+2}+5x^2\sum_{n\ge0}y_{n+1}x^{n+1}-2x^3\sum_{n\ge0}y_nx^n=x^3\sum_{n\ge0}(2x)^n.$$ This is $$(f(x)-y_2x^2-y_1x-y_0)-4x(f(x)-y_1x-y_0)+5x^2(f(x)-y_0)-2x^3f(x)=\frac{x^3}{1-2x},$$ which is $$(1-4x+5x^2-2x^3)f(x)+(4y_1-y_2-5y_0)x^2+(4y_0-y_1)x-y_0=\frac{x^3}{1-2x}.$$ Then taking $a_2=4y_1-y_2-5y_0$, $a_1=4y_0-y_1$, $a_0=-y_0$, we have $$f(x)=\frac{1}{1-4x+5x^2-2x^3}\cdot\frac{x^3+(2x-1)(a_2x^2+a_1x+a_0)}{1-2x},$$ which is $$f(x)=\frac{(1+2a_2)x^3+(2a_1-a_2)x^2+(a_1-2a_0)x-a_0}{(1-2x)(1-4x+5x^2-2x^3)}.$$ Upon simplifying, this becomes $$f(x)=\frac{(1-10y_0+8y_1-2y_2)x^3+(13y_0+2y_1+y_2)x^2+(6y_0-y_1)x+y_0}{(1-2x)(1-4x+5x^2-2x^3)}.$$ Nicely enough, the denominator factors as $1-4x+5x^2-2x^3=(1-2x)(1-x)^2$, so that $$f(x)=\frac{(1-10y_0+8y_1-2y_2)x^3+(13y_0+2y_1+y_2)x^2+(6y_0-y_1)x+y_0}{(1-x)^2(1-2x)^2}.$$ Take $u_3=1-10y_0+8y_1-2y_2$, $u_2=13y_0+2y_1+y_2$, $u_1=6y_0-y_1$, $u_0=y_0$. Partial fractions gives $$f(x)=\left(\frac8{2x-1}+\frac4{(2x-1)^2}+\frac4{1-x}+\frac1{(1-x)^2}\right)(u_3x^3+u_2x^2+u_1x+u_0).$$ Then using the geometric series to expand the rational functions, we have $$f(x)=(u_3x^3+u_2x^2+u_1x+u_0)\sum_{n\ge0}[-2^{n+3}+2^{n+2}(n+1)+4+n+1]x^n,$$ which simplifies as $$f(x)=(u_3x^3+u_2x^2+u_1x+u_0)\sum_{n\ge0}[2^{n+2}(n-1)+n+5]x^n.$$ taking $q_n=2^{n+2}(n-1)+n+5$, we get $$\begin{align} f(x)&=(u_3x^3+u_2x^2+u_1x+u_0)\sum_{n\ge0}q_nx^n\\ &=\sum_{n\ge0}u_3q_nx^{n+3}+\sum_{n\ge0}u_2q_nx^{n+2}+\sum_{n\ge0}u_1q_nx^{n+1}+\sum_{n\ge0}u_0q_nx^n\\ &=\sum_{n\ge3}u_3q_{n-3}x^n+\sum_{n\ge2}u_2q_{n-2}x^{n}+\sum_{n\ge1}u_1q_{n-1}x^{n}+\sum_{n\ge0}u_0q_nx^n\\ &=\sum_{n\ge3}(u_3q_{n-3}+u_2q_{n-2}+u_1q_{n-1}+u_0q_n)x^n+(u_2q_0+u_1q_1+u_0q_2)x^2+(u_1q_0+u_0q_1)x+u_0q_0. \end{align}$$ Comparing coefficients of the left and right sides, we get $$y_n=u_3q_{n-3}+u_2q_{n-2}+u_1q_{n-1}+u_0q_n,\qquad n\ge3,$$ and it is easy to check that the initial values $y_2=u_2q_0+u_1q_1+u_0q_2$, $y_1=u_1q_0+u_0q_1$, $y_0=u_0q_0$ are satisfied. Plugging in the values for $u_3,u_2,u_1,u_0$ and simplifying, $$y_n=q_{n-3}+(q_n+6q_{n-1}+13q_{n-2}-10q_{n-3})y_0+(-q_{n-1}+2q_{n-2}+8q_{n-3})y_1+(q_{n-2}-2q_{n-3})y_2.$$ This is $$y_n=\\ 2^{n-1}(n-4)+n+2+[2^n(34n-87)+10n+54]y_0+[2^{n+1}(2n-9)+9n+18]y_1\\ +[2^n-n-1]y_2, $$ which is equivalent to $$y_n= 2^{n-1}\Big[(34y_0+8y_1)n-4-87y_0-36y_1+2y_2\Big]\\ +(1+10y_0+9y_1-y_2)n+2+54y_0+18y_1-y_2,$$ which is of the form $y_n=2^n(an+b)+cn+d$ for constants $a,b,c,d$. The only thing left to do is plug in the initial values $y_0,y_1,y_2$.

clathratus
  • 17,161