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:

$$A_{n}=A_{n-1}+2n+1$$ where $$A_1=1$$

Now, if we write the recurrence as:

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

$$A_{n}=A_{n-1}+2n+1$$

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

$$A_{n+1}=A_{n}+2(n+1)+1$$

Subtracting the former from the latter, we obtain:

$$A_{n+1}=2A_{n}-A_{n-1}+2$$

$$A_{n+2}=2A_{n+1}-A_{n}+2$$

Subtracting the former from the latter, we obtain:

$$A_{n+2}=3A_{n+1}-3A_{n}+A_{n-1}$$

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

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

$$A_n=k_1+k_2n+k_3n^2$$

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

We are given:

$$A_1=1$$

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

$$A_2=1+2(2)+1=6$$

$$A_3=6+2(3)+1=13$$

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

$$A_1=k_1+k_2\cdot1+k_3\cdot1^2=k_1+k_2+k_3=1$$

$$A_2=k_1+k_2\cdot2+k_3\cdot2^2=k_1+2k_2+4k_3=6$$

$$A_3=k_1+k_2\cdot3+k_3\cdot3^2=k_1+3k_2+9k_3=13$$

Solving this system, we find:

$$k_1=-2,\,k_2=2,\,k_3=1$$

and so the closed form for the recurrence is:

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