How to find recurrence relation from a closed form? 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?
 A: 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$.
A: 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.
A: 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$.
