A Formula for $a_n$: $c_n + d_n$

[anemone]

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.

 

[mente oscura]

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.

Spoiler

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]

Here is my solution:

Spoiler

Let's rewrite the recurrence as:

$$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:

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

We may write the original recursion as:

$$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:

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

Using the given initial values, we find:

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

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

From this 2X2 linear system, we find:

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

Hence:

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

Now, we may arrange this as:

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

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

If we define:

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

we then have:

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

And so by superposition we have the general form:

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

Using the initial value we obtain:

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

Hence:

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

 

[anemone]

Hello.

Spoiler

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:

Spoiler

Let's rewrite the recurrence as:

$$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:

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

We may write the original recursion as:

$$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:

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

Using the given initial values, we find:

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

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

From this 2X2 linear system, we find:

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

Hence:

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

Now, we may arrange this as:

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

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

If we define:

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

we then have:

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

And so by superposition we have the general form:

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

Using the initial value we obtain:

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

Hence:

$$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!(Sun)