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

1. ## 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.

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

3. My mistake was thinking you can't use the statement your trying to prove. But with induction you can. Thanks.

4. But it is perfectly valid to show that what you are given is a solution to an equation by putting it into the equation.

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.