Explicit formula for a recurrance relationship $A_n = A_{n-1} + 2n + 1$

Question

$$a_n = a_{n-1} + 2n + 1 $$ $$ a_0 = 1 $$ $$ a_1 = 4 $$ $$ a_2 = 9 $$

I know the basics of how to use characteristic polynomials, but I'm not sure how the $2n$ would be represented in the characteristic polynomial.

Essentially, the question I'm working on trying to answer is being able to generate all perfect squares within a range [A-B] efficiently, and I saw this recurrence relationship. Any help on how to turn this into an explicit formula? Or how else to tackle this problem?

Thank you!

Answer 1

Hint:

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

Take the sum of both sides from $n=1$ to $n=x$, looks to me like a telescoping series on the left.

If you go through the telescoping sum process you will see:

$$\sum_{n=1}^{x} (a_{n}-a_{n-1})= a_x-a_0=a_x-1$$

Now can you take the right hand sum, and equate your two results?

Answer 2

I'm not exactly sure what it is you're looking for, but you might proceed, in pseudocode, as follows:

k = ceil(sqrt(A))
Sk = k^2
while (Sk <= B) {
    output Sk
    Sk = Sk+2k+1
    k = k+1
}

Answer 3

Note that $a_n-a_{n-1}=2n-1$ implies $a_n-a_0=\sum_{k=1}^n(a_k-a_{k-1})=\sum_{k=1}^n(2k-1)=n^2.$