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.
