Stephen's question at Yahoo Answers regarding an inhomogeneous linear recurrence

[MarkFL]

Here is the question:

Find The Closed Form?

A1 = 1
an-1 + 2n+1
I know how to get the sequence but I don't know how to write the closed form.

Here is a link to the question:

Find The Closed Form? - Yahoo! Answers

I have posted a link there to this topic so the OP can find my response.

 

[MarkFL]

Hello Stephen,

We are given the recurrence:

\(\displaystyle A_{n}=A_{n-1}+2n+1\) where \(\displaystyle A_1=1\)

Now, if we write the recurrence as:

\(\displaystyle A_{n}-A_{n-1}=2n+1\)

we can see that the difference between two successive terms is a linear function in $n$ and so we know the closed form will be quadratic. Let's take the time to look at a method called symbolic differencing to show that this must be true. Let's begin with the given recurrence:

\(\displaystyle A_{n}=A_{n-1}+2n+1\)

We may now increase $n$ by one to write the recurrence equivalently as:

\(\displaystyle A_{n+1}=A_{n}+2(n+1)+1\)

Subtracting the former from the latter, we obtain:

\(\displaystyle A_{n+1}=2A_{n}-A_{n-1}+2\)

\(\displaystyle A_{n+2}=2A_{n+1}-A_{n}+2\)

Subtracting the former from the latter, we obtain:

\(\displaystyle A_{n+2}=3A_{n+1}-3A_{n}+A_{n-1}\)

We now have a homogeneous recurrence, whose associated characteristic equation is:

\(\displaystyle r^3-3r^2+3r-1=(r-1)^3=0\)

Because the characteristic roots are $r=1$ of multiplicity 3, we know the closed form is:

\(\displaystyle A_n=k_1+k_2n+k_3n^2\)

where the parameters $k_i$ may be determined by initial values.

We are given:

\(\displaystyle A_1=1\)

and so using the original inhomogeneous recurrence, we may compute the next two terms:

\(\displaystyle A_2=1+2(2)+1=6\)

\(\displaystyle A_3=6+2(3)+1=13\)

Now we have enough values to determine the parameters. We obtain the following 3X3 system:

\(\displaystyle A_1=k_1+k_2\cdot1+k_3\cdot1^2=k_1+k_2+k_3=1\)

\(\displaystyle A_2=k_1+k_2\cdot2+k_3\cdot2^2=k_1+2k_2+4k_3=6\)

\(\displaystyle A_3=k_1+k_2\cdot3+k_3\cdot3^2=k_1+3k_2+9k_3=13\)

Solving this system, we find:

\(\displaystyle k_1=-2,\,k_2=2,\,k_3=1\)

and so the closed form for the recurrence is:

\(\displaystyle A_n=-2+2n+n^2=n^2+2n-2\)

To Stephen and any other guests viewing this topic, I invite and encourage you to post other recurrence or difference equation questions in our http://www.mathhelpboards.com/f15/ forum.

Best Regards,

Mark.