How to find recurrence relation from a closed form?

Question

I don't understand how to find recurrence relation from a sequence. Suppose I have $A(n)=n^2-n, n>0.$ How do I find the recurrence relation of this sequence?

Answer 1

There are no hard & fast general rules I know which you can follow due to the many different possible expressions which you may encounter. Each case, at least to a certain extent, is somewhat unique.

You could just do as Gae.S.'s question comment suggests of just using something like $A(n) = n^2 - n + 0 \cdot A(n-1)$. However, if you wish to use a non-zero multiple of the previous value, in general, I would first check the difference between consecutive values to see if I can relate it to $n$, the previous value or something else like that. For your particular case of

$$A(n) = n^2 - n \tag{1}\label{eq1A}$$

I would check on

$$\begin{equation}\begin{aligned} A(n+1) - A(n) & = ((n+1)^2 - (n+1)) - (n^2 - n) \\ & = (n^2 + 2n + 1 - (n+1)) - (n^2 - n) \\ & = (n^2 + n) - (n^2 - n) \\ & = 2n \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

This shows that one possibility is to use

$$A(n+1) = A(n) + 2n \tag{3}\label{eq3A}$$

for $n \gt 0$, and with an initial condition of $A(1) = 0$.

Answer 2

hint

$$n^2-n-A(n)=0$$

thus

$$n=\frac{1+\sqrt{1+4A(n)}}{2}$$ and $$n+1=\frac{1+\sqrt{1+4A(n+1)}}{2}$$

The difference will give you the relation.

Answer 3

Your $A(n)$ satisfies this homogeneous linear recurrence relation with constant coefficients:

$$A(n)=3A(n-1)-3A(n-2)+A(n-3)$$

with initial values $A(1)=0, A(2)=2$, and $A(3)=6.$

---

Derivation:

$A(n)-A(n-1)=2n-2$

$A(n-1)-A(n-2)=2n-4$

so (subtracting)

$A(n)-2A(n-1)+A(n-2)=2$

$A(n-1)-2A(n-2)+A(n-3)=2$

so (subtracting)

$A(n)-3A(n-1)+3(n-2)-A(n-3)=0$.