# Solution to Recurrence Relation

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?

-
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

## 2 Answers

$$a_{n+1}=(n+1)^3=n^3+3n^2+3n+1=a_n+3n^2+3n+1$$

-
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$$

-
@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