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

  • Thread starter Thread starter MarkFL
  • Start date Start date
  • Tags Tags
    Linear Recurrence
AI Thread Summary
The discussion addresses Stephen's question about finding the closed form of the recurrence relation A_n = A_{n-1} + 2n + 1 with A_1 = 1. The analysis shows that the closed form will be quadratic due to the linear difference between successive terms. By applying symbolic differencing and solving a system of equations derived from initial values, the parameters are determined as k_1 = -2, k_2 = 2, and k_3 = 1. Consequently, the closed form is established as A_n = n^2 + 2n - 2. The conversation encourages further inquiries into recurrence relations in a dedicated math forum.
MarkFL
Gold Member
MHB
Messages
13,284
Reaction score
12
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.
 
Mathematics news on Phys.org
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.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
Back
Top