Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

Question

General solution is:
$a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$
Can you give me some tips on solving this?
Any help would be appreciated.

Answer 1

If you have the recurrence relation

$\displaystyle\color{green}{ a_{n+1}=2a_n+k+ln+\frac{1}{3}(2^n)}$ where $l\ne0$,

then the general solution will be of the form

$a_n=C(2^n)+A+Bn+\frac{1}{3}(n2^{n-1})$,

where the first term comes from the solution to the homogeneous recurrence relation,

the next two terms correspond to the terms $k+ln$, and the last term corresponds to $\frac{1}{3}(2^n)$.

Answer 2

The answer given by @user84413 is slightly simpler than the initial relationship but still has two non constant coefficients.

It is possible to get a third order constant coefficients affine recurrence relationship (relationship (6) below) generating sequence $(a_n)$.

Here is a method for obtaining it.

Consider the two following auxiliary sequences:

$$b_n:=a_{n+1}-a_n=B+C 2^n+\dfrac{1}{6}(n+2)2^n \ \ \ (1)$$

thus,

$$c_n:=b_n-B \ \ \ (2)$$

is of the form $c_n=(D+En)2^n \ \ \ (*)$.

Thus sequence $c_n$ is governed by the following second order recurrence relationship

$$c_{n+2}=4c_{n+1}-4c_n \ \ \ \ (3) $$

Remark 1: (3) is a direct consequence of (*) by combining particular relationships :

$$\begin{cases} c_{n+2} & = & (D+En+2E)2^{n+2}\\ c_{n+1} & = & (D+En+E)2^{n+1}\\ c_{n} & = & (D+En)2^n \end{cases}$$

Remark 2: Relationship (3) is not at all unexpected: it is connected to results governing the characteristic equation of second order linear recurrences having a double root (see for example here).

Remark 3: We have not yet taken initial conditions into account. This will be done in a last step.

Plugging in relationship (2) into (3), one gets:

$$b_{n+3}=4b_{n+2}-4b_{n+1} + B\ \ \ \ (4) $$

Using (1), (4) gives:

$$a_{n+3}-a_{n+2}=4(a_{n+2}-a_{n+1})-4(a_{n+1}-a_{n}) + B\ \ \ \ (5) $$

yielding final recurrence relationship:

$$\displaystyle\color{red}{a_{n+3}=5a_{n+2}-8a_{n+1}+4a_{n} + B}\ \ \ \ (6) $$

with initial values

$$\begin{cases}a_1 & = & A+B+2C+1/3\\a_2 & = & A+2B+4C+4/3\\ a_3 & = & A+3B+8C+4\end{cases}$$

Answer 3

Your recurrence solution shows 2 roots, $r_1 = 1$ and $r_2 = 2$, each with multiplicity $2$. So the characteristic equation of the linear recurrence is

$$(x - r_1)^2~(x - r_2)^2 = x^4 - 6x^3 + 13x^2 - 12x + 4$$

So a simple linear recurrence that will have this as a solution is :

$$H(n) = S_{n + 4} - 6~S_{n + 3} + 13~S_{n + 2} - 12~S_{n + 1} + 4~S_{n + 0} = 0 \tag{T1}$$

Now a nonhomogenous equation is an equation of the form:

$$\text{Linear Terms } = \text{ Self Linear Terms} \tag{T2}$$

Self linear terms are terms $f_1(n),~f_2(n),~\dots$ such that $f_1(n+1) + f_2(n+1) + \dots$ can be written as a linear combination of $f_1(n),~f_2(n),~\dots$. Linear terms are just terms that are of the form $\sum_{k = 0}^m~A_k~S_{n + k}$.

There several possible equations of the form of (T2) that characterize a sequence equivalent to (T1). But the linear terms of each of them will evenly divide the characteristic equation of (T1) (this is easy to prove if you presume the cancellation technique in (T4), but maybe not so easy to prove without that assumption). So, the candidate characteristics equations of the linear parts are:

$$(x - 1)^{k_1}~(x - 2)^{k_2} \tag{T3}$$

Where $k_1$ is $0$, $1$, or $2$, same restrictions on $k_2$. That leaves $9$ possible linear parts:

$$\begin{array} {rl|l} & & \text{Characteric equation} \\ \hline S_{n + 1} - S_{n} &= \text{Self Linear Terms} & (x - 1) \\ S_{n + 1} - 2~S_{n} &= \text{Self Linear Terms} & (x - 2) \\ \vdots \\ S_{n + 3} - 4~S_{n + 2} + 5~S_{n + 1} - 2~S_{n} &= \text{Self Linear Terms} & (x - 1)^2(x - 2) \\ \vdots \\ \end{array}$$

Now that limits our possible recursions, but it still remains to determine which ones can actually yield (T1). For a given equation above, calling the linear part $F(n)$ and the self linear part $G(n)$, it can be turned into (T1) if it can be solved for some $A$:

$$A_0~F(n + 0) + A_1~F(n + 1) + \dots + A_k~F(n + k) = H(n) \tag{T4}$$ $$A_0~G(n + 0) + A_1~G(n + 1) + \dots + A_k~G(n + k) = 0 \tag{T5}$$

Taking, for example, $F(n) = S_{n + 1} - S_{n}$, we can solve to find:

$$-4~F(n) + 8~F(n + 1) - 5~F(n + 2) + 1~F(n + 3) = H(n)$$

And choosing any self linear terms that makes (T5) true will work, for example, $G(n) = 2^n$ works nicely, giving overall:

$$S_{n + 1} - S_{n} = 2^n \tag{T6}$$

The problem with the (T6) is that it might not give enough initial conditions to specify the sequence intended by the initial conditions that weren't but could have been specified by the original recursion solution. But that's ok, there are 8 more choices, including (T1) itself. Here is it worked out again with a different option:

$$F(n) = S_{n + 3} - 4~S_{n + 2} + 5~S_{n + 1} - 2~S_{n}$$ $$-2~F(n) + 1~F(n + 1) = H(n)$$ $$G(n) = 2^n \implies -2~G(n + 1) + G(n) = 0$$

$$S_{n + 3} - 4~S_{n + 2} + 5~S_{n + 1} - 2~S_{n} = 2^n \tag{T7}$$