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,

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

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