# Find a_n

#### anemone

##### MHB POTW Director
Staff member
Let $a_0=2$, $a_1=3$, $a_2=6$, and for $n \ge 3$, $a_n=(n+4)a_{n-1}-4na_{n-2}+(4n-8)a_{n-3}$.

The first few terms are $2,\;\;3,\;\;6,\;\;14, \;\;40, \;\;152, \;\;784, \;\;5168,\;\; 40576, \;\;363392$.

Find with proof a formula for $a_n$ of the form $a_n=c_n+d_n$, where $c_n$ and $d_n$ are well-known sequences.

Last edited:

#### mente oscura

##### Well-known member
Let $a_0=2$, $a_1=3$, $a_2=6$, and for $n \ge 3$, $a_n=(n+4)a_{n-1}-4na_{n-2}+(4n-8)a_{n-3}$.

The first few terms are $2,\;\;3,\;\;6,\;\;14, \;\;40, \;\;152, \;\;784, \;\;5168,\;\; 40576, \;\;363392$.

Find with proof a formula for $a_n$ of the form $a_n=c_n+d_n$, where $c_n$ and $d_n$ are well-known sequences.
Hello.

I guessed the sequences, because I have not been able to prove it.I thought that it could be a factor involved, and, then, by differences I found with another string.

$$a_n=2^n+n!$$

Regards.

#### MarkFL

##### Administrator
Staff member
Here is my solution:

Let's rewrite the recurrence as:

$$\displaystyle a_{n}-na_{n-1}=4\left(a_{n-1}-(n-1)a_{n-2} \right)-4\left(a_{n-2}-(n-2)a_{n-3} \right)$$

Now, if we define:

$$\displaystyle b_{n}=a_{n}-na_{n-1}$$

We may write the original recursion as:

$$\displaystyle b_{n}=4b_{n-1}-4b_{n-2}$$

This is a linear homogenous recursion with the repeated characteristic root $r=2$. Hence the closed form for $b_n$ is:

$$\displaystyle b_{n}=(A+Bn)2^n$$

Using the given initial values, we find:

$$\displaystyle b_1=a_1-a_0=3-2=1=(A+B)2$$

$$\displaystyle b_2=a_2-2a_1=6-6=0=(A+2B)4$$

From this 2X2 linear system, we find:

$$\displaystyle A=1,\,B=-\frac{1}{2}$$

Hence:

$$\displaystyle b_{n}=2^n-n2^{n-1}=a_{n}-na_{n-1}$$

Now, we may arrange this as:

$$\displaystyle a_{n}-2^{n}=n\left(a_{n-1}-2^{n-1} \right)$$

This implies one solution is $$\displaystyle c_n=2^n$$

If we define:

$$\displaystyle d_n=a_{n}-2^{n}$$

we then have:

$$\displaystyle d_{n}=nd_{n-1}\implies d_n=Cn!$$

And so by superposition we have the general form:

$$\displaystyle a_n=2^n+Cn!$$

Using the initial value we obtain:

$$\displaystyle a_0=2=2^0+C0!=1+C\implies C=1$$

Hence:

$$\displaystyle a_n=2^n+n!$$

#### anemone

##### MHB POTW Director
Staff member
Hello.

I guessed the sequences, because I have not been able to prove it.I thought that it could be a factor involved, and, then, by differences I found with another string.

$$a_n=2^n+n!$$

Regards.
Well, even though you didn't provide any proof, your answer is correct and since you've been actively engaged with our site for quite some time and solving many challenge problems in the Challenge Questions and Puzzles sub-forum, I would give allowance to you and hence I would declare it here that you got full mark for that!

Thanks for participating, mente!

Here is my solution:

Let's rewrite the recurrence as:

$$\displaystyle a_{n}-na_{n-1}=4\left(a_{n-1}-(n-1)a_{n-2} \right)-4\left(a_{n-2}-(n-2)a_{n-3} \right)$$

Now, if we define:

$$\displaystyle b_{n}=a_{n}-na_{n-1}$$

We may write the original recursion as:

$$\displaystyle b_{n}=4b_{n-1}-4b_{n-2}$$

This is a linear homogenous recursion with the repeated characteristic root $r=2$. Hence the closed form for $b_n$ is:

$$\displaystyle b_{n}=(A+Bn)2^n$$

Using the given initial values, we find:

$$\displaystyle b_1=a_1-a_0=3-2=1=(A+B)2$$

$$\displaystyle b_2=a_2-2a_1=6-6=0=(A+2B)4$$

From this 2X2 linear system, we find:

$$\displaystyle A=1,\,B=-\frac{1}{2}$$

Hence:

$$\displaystyle b_{n}=2^n-n2^{n-1}=a_{n}-na_{n-1}$$

Now, we may arrange this as:

$$\displaystyle a_{n}-2^{n}=n\left(a_{n-1}-2^{n-1} \right)$$

This implies one solution is $$\displaystyle c_n=2^n$$

If we define:

$$\displaystyle d_n=a_{n}-2^{n}$$

we then have:

$$\displaystyle d_{n}=nd_{n-1}\implies d_n=Cn!$$

And so by superposition we have the general form:

$$\displaystyle a_n=2^n+Cn!$$

Using the initial value we obtain:

$$\displaystyle a_0=2=2^0+C0!=1+C\implies C=1$$

Hence:

$$\displaystyle a_n=2^n+n!$$
Well done, MarkFL! I just love to read your solution posts because they are always so nicely written and well explained! Bravo, my sweetest global moderator!