Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I asked a question previously, about how to describe

$$ f(n) = n^3 $$

As a recurrence relation. I was, quite rightly, given $a_1=1$ and $a_{n+1}=a_n+3n^2+3n+1$.

I have attempted to solve it, using forward substitution, but I'm having trouble.

I started out by assuming a solution to this recurrence relation was $n^3$. I then attempted a proof by induction that $a_n + 2 = (n+1)^3$

And now I am stuck out of my mind! Can anyone help me out here?

share|cite|improve this question
What kind of arecurrence relation you are looking for? – Mhenni Benghorbal May 2 '13 at 0:44
If $a_{n+2}=(n+1)^3$, you've gone wrong. You want $a_{n+1}=(n+1)^3$. – Thomas Andrews May 2 '13 at 1:53
(I'm assuming you meant $a_{n+2}$ rather than $a_n+2$.) – Thomas Andrews May 2 '13 at 1:54
up vote 3 down vote accepted


share|cite|improve this answer
How did you go from $(n + 1)^3$ to $n^3 + 3n^2 + 3n + 1$? – notverygoodatmaths May 1 '13 at 23:10
Just expand $(n+1)^3$ – user63181 May 1 '13 at 23:11
@ChrisCooney or use Newton's Binomial Theorem. – Git Gud May 1 '13 at 23:11
It should be written exactly backwards for a induction step proof. – vonbrand May 1 '13 at 23:15
@vonbrand Yeah I got that much :P Sorry, this is really basic but I have gaping holes in my math knowledge! Thankyou for the answer, I will accept in 5 minutes when it lets me. – notverygoodatmaths May 1 '13 at 23:16

I don't understand your question. If you want to show that the solution to the recurrence $$a_{n+1} = a_n + 3n^2 + 3n + 1 \,\,\,\,\, a_1 = 1$$ is $a_n = n^3$, here is a way out.

We have $$a_{n+1} + n^3 = a_n + \overbrace{n^3 + 3n^2 + 3n + 1}^{(n+1)^3} = a_n + (n+1)^3$$ Now if we call $b_n = a_n - n^3$, we have $$b_{n+1} = b_n \,\, \text{ and } \,\, b_1 = a_1 - 1 = 0$$ Hence, we get $$b_{n+1} = b_n = b_{n-1} = \cdots = b_1 =0$$ This implies $$a_n = n^3$$

share|cite|improve this answer
@user177562 The OP wants to find a recurrence relation for $f(n)=n^3$. – Git Gud May 1 '13 at 23:12
@GitGud What? ${}$ – user17762 May 1 '13 at 23:20
I meant I made a mistake when typing your name on the comment above. – Git Gud May 1 '13 at 23:22
@GitGud I think he said he already had the recurrence, he wanted to find out how to show it worked – Thomas Andrews May 2 '13 at 1:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.