2
$\begingroup$

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?

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

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

Improve this answer
$\endgroup$
  • $\begingroup$ How did you go from $(n + 1)^3$ to $n^3 + 3n^2 + 3n + 1$? $\endgroup$ – notverygoodatmaths May 1 '13 at 23:10
  • $\begingroup$ Just expand $(n+1)^3$ $\endgroup$ – user63181 May 1 '13 at 23:11
  • $\begingroup$ @ChrisCooney or use Newton's Binomial Theorem. $\endgroup$ – Git Gud May 1 '13 at 23:11
  • 1
    $\begingroup$ It should be written exactly backwards for a induction step proof. $\endgroup$ – vonbrand May 1 '13 at 23:15
  • $\begingroup$ @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. $\endgroup$ – notverygoodatmaths May 1 '13 at 23:16
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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