# Don't know what to do here, recursive problem

• Oct 12th 2009, 11:20 AM
Don't know what to do here, recursive problem
The succession [Xsubn] is defined as

Xsub0 = 0, Xsub(n+1) = Xsubn + n(n+1)

Show that Xsubn = (1/3)(n-1)n(n+1).

I am assuming I am not allowed to use what I am demonstring as part of the proof. No clue what do despite staring at it for 15 minutes.
• Oct 12th 2009, 11:51 AM
Taluivren
Hi,

$x_0 = 0$, $x_{n+1} = x_n + n(n+1)$
and we have to prove $x_n = \frac{1}{3}(n-1)n(n+1)$.

We proceed by induction:
$n=0$ .. $x_0 = \frac{1}{3}(0-1)\cdot 0\cdot (0+1) =0$ so the base case holds.

suppose the statement holds for $n$ and let's prove it holds for $n+1$:
$x_{n+1}= x_n + n(n+1) = \frac{1}{3}(n-1)n(n+1) +n(n+1)$ (by induction hypotheses)
$= n(n+1)(\frac{1}{3}(n-1)+1) = n(n+1)(\frac{1}{3}n+\frac{2}{3}) = \frac{1}{3}n(n+1)(n+2)$
$=\frac{1}{3}((n+1)-1)(n+1)((n+1)+1)$ so the inductive step is done.
• Oct 12th 2009, 12:30 PM
For example, it would be very difficult to solve $x^5- 6x^2- 3x- 2= 0$ but it is very easy to show that x= 2 is a solutions: [tex]2^2- 6(2^2)- 3(2)- 6= 32- 24- 6- 2= 0.
Similarly, here, you are not asked to solve the recursion, just to show that $x_n= \frac{(n-1)n(n+1)}{3}$ satisfies it. And that is basically what Taluivren did.