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

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

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

suppose the statement holds for $\displaystyle n$ and let's prove it holds for $\displaystyle n+1$:
$\displaystyle x_{n+1}= x_n + n(n+1) = \frac{1}{3}(n-1)n(n+1) +n(n+1)$ (by induction hypotheses)
$\displaystyle = 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)$
$\displaystyle =\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 $\displaystyle 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 $\displaystyle x_n= \frac{(n-1)n(n+1)}{3}$ satisfies it. And that is basically what Taluivren did.