How can I solve this linear recurrence relation?

Question

My problem is: this given recurrence relation: $$y_{n+1}-\frac{n+2}{2}\cdot y_n = (n+1)(n+2)\cdot 3^n$$ for all: $n\ge 0$ and $y_0 = 0$

I need to find the explicit form and the general solution.

My Approach was: I can see, this is a linear recurrence relation. Due to the right side of the equation, it must be a inhomogeneous equation. So I think the way should be to find a general solution for the homogeneous equation first. And then finding a Special solution for the inhomogenous equation and finally finding my answer in adding both solutions.
And here starts the trouble. I've read my seminar literature twice, but I keep failing in performing the described steps.

In my next try, I concentrated on the given $y_0 = 0$. Through inserting I found out for $n = 0$ $$y_{0+1}-\frac{0+2}{2}\cdot 0 = (0+1)(0+2)\cdot 3^0$$ $$y_{1} = 2$$ And inserting again for $n = 1$ i get: $$y_{1+1}-\frac{1+2}{2}\cdot 2 = (1+1)(1+2)\cdot 3^1$$ $$y_{2}-\frac{3}{2}\cdot 2 = 6\cdot 3$$ $$y_{2} = 21$$

That might be nice, but it seems it doesnt bring me to any solution for the original Task. How can I get the solutions I need?

Update: bounty set... rather than just a solution I could use a explanation how to derive the result.

What would be the way to get the solution for the homogeneous relation and how to get the Special (or it is called specific?) solution for the inhomogeneous relation.

Answer 1

Direct Method

Putting $y_n=(n+1)!2^{1-n}x_n$ the recurrence relation $$ y_{n+1}−\frac{n+2}{2}y_n=(n+1)(n+2)3^n\tag 1 $$ with initial condition $y_0=0$ forall $n\ge 0$, becomes $$ x_{n+1}=x_n+\frac{6^n}{n!}. \tag 2 $$ with initial condition $x_0=\frac{y_0}{2}=0$. This is a non-homogeneous recurrence relation with non-homogeneous term $\xi_n=\frac{6^n}{n!}$ that can be solved directly in a very simple way.

We know that the general solution to a non-homogeneous recurrence relation is the sum of the general solution to the associated homogeneous recurrence and any particular solution to the non-homogeneous recurence. So if $a_n$ is a solution to the associated homogeneous recurrence $x_{n+1}-x_n=0$, and $b_n$ is a particular solution to the non-homogeneous recurrence $x_{n+1}-x_n=\xi_n$, then $a_n+b_n$ is the general solution to the non-homogeneous recurrence.

The general solution $a_n$ of the associated homogeneous recurrence relation $x_{n+1}-x_n=0$ is trivial, i.e. $a_n=0$ for all $n\ge0$. Infact the characteristic equation is $\lambda-1=0$, so that $a_n=\alpha^1$ and from the initial condition $x_0=0$, we have $\alpha=0$, i.e $a_n=0$.

Now we have to find a particular solution $x_n=b_n$ of the relation (2). Observing that the term $\xi_n=\frac{6^n}{n!}$ is the $n$-th term of the exponential series, and that the difference between the $n+1$-th term $b_{n+1}$ and the $n$-th term $b_n$ must be the $n$-th term of the exponential series, we may take a particular solution as a truncated exponential series $$ b_n=\sum_{n=0}^{n-1}\frac{6^k}{k!}. $$ It's evident that $b_n$ satisfies the relation(2): $$ \begin{align} b_{n+1}-b_n&=\sum_{k=0}^{n}\frac{6^k}{k!}-\sum_{k=0}^{n-1}\frac{6^k}{k!}\\ &=\left(1+\tfrac{6^1}{1!}+\cdots+\tfrac{6^{n-1}}{(n-1)!}+\frac{6^{n}}{n!}\right)-\left(1+\tfrac{6^1}{1!}+\cdots+\tfrac{6^{n-1}}{(n-1)!}\right)\\ &=\frac{6^{n}}{n!}. \end{align} $$

So the general solution of (2) is $$ x_n=a_n+b_n=\sum_{k=0}^{n-1}\frac{6^k}{k!}.\tag 3 $$

Finally the general solution of (1) is $$ y_n=(n+1)!2^{1-n}\sum_{k=0}^{n-1}\frac{6^k}{k!}\tag 4 $$ for $n\ge 1$ and $y_0=0$.

Ordinary Generating Function

If you prefer to work with generating function, multiply the recurrence (2) by $z^n$ and sum over $n$ $$ \sum_{n=0}^\infty x_{n+1}z^n-\sum_{n=0}^\infty x_{n}z^n=\sum_{n=0}^\infty \frac{6^n}{n!}z^n $$ and put $X(z)=\sum_{n=0}^{\infty} x_nz^n$ for $|z|<1$; we have $$ \frac{1}{z}(X(z)-x_0)-X(z)=\operatorname{e}^{6z} $$ that is $$ X(z)=\frac{z}{1-z}\cdot \operatorname{e}^{6z}. $$ Observing that $\frac{z}{1-z}=\sum_{n=1}^{\infty}z^n$, then $x_n$ is the discrete convolution of the discrete Heaviside step function $h_n$ and the sequence $\xi_n=\frac{6^n}{n!}$, that is $$x_n=\sum_{k=0}^{n-1}\frac{6^k}{k!}$$

Other Representations

Recalling that the incomplete gamma function $\Gamma(\alpha,x)$ is given by $$ \Gamma(\alpha,x)=\int_x^\infty t^{\alpha-1}\operatorname{e}^{-t}\operatorname{d}t $$ and that for $\alpha$ an integer $n$ $$ \Gamma(n,x)=(n-1)!\operatorname{e}^{-x}\sum_{k=0}^{n-1}\frac{x^k}{k!}=(n-1)!\operatorname{e}^{-x}e_{n-1}(x), $$ where $e_n(x)=\displaystyle\sum_{k=0}^{n-1}\frac{x^k}{k!}$ is the exponential sum function, the general solution (4) can be expressed as

$$ y_n=(n+1)!2^{1-n}e_{n-1}(6) =\operatorname{e}^{6}2^{1-n}(n+1)n\Gamma(n,6)\tag 5 $$

Using the Generalized Exponential Integral $E_n$ function defined as $$ E_n(x)= \int_1^\infty\frac{\operatorname{e}^{-xt}}{t^n}\operatorname{d}⁡t= x^{n-1}⁢\Gamma⁡(1-n,x) $$ the solution (5) can be expressed as

$$ y_n=\operatorname{e}^{6}2^{1-n}(n+1)n6^nE_{1-n}(6).\tag 6 $$

Finally, putting all together the general solution of (1) can be represented as

$$ y_n=\operatorname{e}^{6}2^{1-n}(n+1)n\Gamma(n,6)=\operatorname{e}^{6}2^{1-n}(n+1)n6^nE_{1-n}(6).\tag 7 $$

Answer 2

Set $x_n=y_n\frac{2^n}{(n+1)!}$. Then $$x_{n+1}=x_n+\frac{2^{n+1}3^n}{n!}$$ etc.

Answer 3

Even though this has been answered with a useful hint that basically says it all, the OP seems to ask for more detail, so here are a few additional steps.

The trick is to use exponential generating functions. First divide the recurrence by $(n+2)(n+1),$ to get

$$\frac{y_{n+1}}{(n+2)(n+1)} - \frac{1}{2} \frac{y_n}{(n+1)} = 3^n.$$ The exponential generating function that we will use is $$A(q) = \sum_{n\ge 1} \frac{y_n}{(n+1)!} q^n.$$ We build a functional equation for $A(q)$ by multiplying the recurrence by $q^{n+1}/n!$ and summing over $n\ge 1$ to get $$\sum_{n\ge 1} \frac{y_{n+1}}{(n+2)!} q^{n+1} - \frac{1}{2} q\sum_{n\ge 1} \frac{y_n}{(n+1)!} q^n = \sum_{n\ge 1} \frac{3^n}{n!} q^{n+1}.$$ This is $$A(q) - q - \frac{1}{2} q A(q) = q \sum_{n\ge 1} \frac{3^n}{n!} q^n = q \left(e^{3q} - 1\right).$$ This gives $$\left(1-\frac{1}{2}q\right) A(q) = q \times e^{3q} \quad\text{or}\quad A(q) = q \frac{e^{3q}}{1-\frac{1}{2} q}.$$ To conclude note that $y_n = (n+1)! [q^n] A(q)$ so that $$y_0 = [q^0] q \frac{e^{3q}}{1-\frac{1}{2} q} = 0$$ and for $n\ge 1$ we have $$(n+1)! [q^n] q \frac{e^{3q}}{1-\frac{1}{2} q} = (n+1)! [q^{n-1}] \frac{e^{3q}}{1-\frac{1}{2} q} = (n+1)! \sum_{k=0}^{n-1} \frac{3^k}{k!} \frac{1}{2^{n-1-k}}$$ yielding the final answer $$y_n = \frac{(n+1)!}{2^{n-1}} \sum_{k=0}^{n-1} \frac{6^k}{k!} \sim \frac{(n+1)!}{2^{n-1}} \exp(6)$$ where we have used the Cauchy product of two sequences. Examining this result we see why ordinary generating functions don't work as well here.

Answer 4

At "how-to-do": I'd try to look at the list of equations for decreasing $n$ and try to make a telescoping sum out of it because that would reduce it to an equation, where on the lhs we have only $y_{n+1}$ and on the rhs an expression free of $y$ which hopefully can be made in a nicer expression depending on the index $n$ such that we can write the general term more easily:

$$ \small \begin{array} {} &\; y_{n+1} &-\frac {n+2}2\cdot y_{n } &\;=& 1\cdot &(n+1)(n+2)\cdot 3^n \\ \frac {n+2}2 &( y_{n } &-\frac {n+1}2\cdot y_{n-1} &)= & \frac {n+2}2 \cdot &(n )(n+1)\cdot 3^{n-1} \\ \frac {n+2}2\frac {n+1}2 & ( y_{n-1} &-\frac {n }2\cdot y_{n-2} &)=& \frac {n+2}2 \frac {n+1}2\cdot & (n-1)(n )\cdot 3^{n-2} \\ \\ \vdots \\ \\ \frac {(n+2)!/2!}{2 ^n} & ( y_{1} &-\frac {2 }2\cdot y_{0} &)=& \frac {(n+2)!/2!}{2^n} \cdot & (1)(2 )\cdot 3^{0} \\ \end{array}$$ and this, when column-wise summed reduces to $y_{n+1}$ on the lhs and some sum on the rhs whose terms are easily recognizable consisting mainly of the binomial-coefficents $$ y_{n+1} = \sum \small \text{<something depending on $n$ >}$$