I've been working on a project, and it's come to that time when I have to prove the run time complexity of an algorithm. I've obtained my metric and those things that have nothing to do with you guys! However, I am stuck describing a pattern as a recurrence relation.
$$ 1, 8, 27, 64, 125, 216, 343, 512... $$
From a little bit of work, I realised that I've got a pattern, where each number is
$$ f(n) = n^3 $$
Now the big problem I'm facing is how to express this as a recurrence relation. Is it possible?
Note that $(n+1)^3-n^3=3n^2+3n+1$. Thus we can let $a_1=1$ and $a_{n+1}=a_n+3n^2+3n+1$ to get the desired recurrence relation.