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:

\(\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]

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:

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

 

[CellCoree]

The formula for $a_n$ can be rewritten as $a_n = (n+4)a_{n-1}-4na_{n-2}+(4n-8)a_{n-3} = (n+4)(a_{n-1}-a_{n-2})-4n(a_{n-2}-a_{n-3})+(4n-8)a_{n-3}$.

Let $b_n = a_{n-1}-a_{n-2}$, then the above formula becomes $a_n = (n+4)b_{n-1}-4n(a_{n-2}-a_{n-3})+(4n-8)a_{n-3}$.

Notice that $b_n$ follows a well-known sequence, the Fibonacci sequence, with $b_1 = a_0-a_{-1} = 2$ and $b_2 = a_1-a_0 = 1$.

Therefore, we can rewrite the formula for $a_n$ as $a_n = (n+4)b_{n-1}-4n(b_{n-2}-b_{n-3})+(4n-8)a_{n-3} = (n+4)b_{n-1}-4nF_{n-1}+(4n-8)a_{n-3}$, where $F_n$ is the $n$th Fibonacci number.

Now, let $c_n = (n+4)b_{n-1}$ and $d_n = -4nF_{n-1}+(4n-8)a_{n-3}$.

We can see that $c_n$ follows a well-known sequence, the sequence of partial sums of the Fibonacci numbers, with $c_1 = 6$ and $c_2 = 12$.

Similarly, $d_n$ follows a well-known sequence, with $d_1 = 0$ and $d_2 = 0$.

Therefore, we have found a formula for $a_n$ of the form $a_n = c_n + d_n$, where $c_n$ and $d_n$ are well-known sequences.

Proof:

We can prove this formula by induction.

Base cases:

For $n=0$, $a_0 = c_0 + d_0 = 2$,