Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
(I'm assuming you meant $a_{n+2}$ rather than $a_n+2$.) –  Thomas Andrews May 2 '13 at 1:54

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
How did you go from $(n + 1)^3$ to $n^3 + 3n^2 + 3n + 1$? –  Chris Cooney May 1 '13 at 23:10
    
Just expand $(n+1)^3$ –  Sami Ben Romdhane May 1 '13 at 23:11
    
@ChrisCooney or use Newton's Binomial Theorem. –  Git Gud May 1 '13 at 23:11
1  
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. –  Chris Cooney May 1 '13 at 23:16

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

share|improve this answer

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

 
discard

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.