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.

Printable View

- Oct 12th 2009, 11:20 AMHeadOnAPikeDon'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 AMTaluivren
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 PMHeadOnAPike
My mistake was thinking you can't use the statement your trying to prove. But with induction you can. Thanks.

- Oct 12th 2009, 07:28 PMHallsofIvy
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.