# Solution to Recurrence Relation

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

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

The general solution to this sort of problem is to write $3n^2+3n+1$ in terms of $\binom{n}{k}$:

$$3n^2+3n+1 = 6\binom{n}{2} + 6\binom{n}{1} + \binom{n}{0}$$

Then you use that $\sum_{j=0}^n \binom{j}{k} = \binom{n+1}{k+1}$.

So $\sum_{j=0}^n 3j^2+3j+1 = 6\binom{n+1}{3} + 6\binom{n+1}{2} + \binom{n}{1}$

Then \begin{align}a_n &= a_0 + \sum_{j=0}^{n-1} 3j^2+3j+1 \\ &=n(n-1)(n-2) + 3n(n-1) + n \\&= (n^3-3n^2+2n) + 3n^2-3n + n \\&= n^3\end{align}

-